#P18711. Teleport

    ID: 18047 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-广度优先搜索坐标变换普通并查集路径压缩按大小合并枚举置位位置

Teleport

Teleport

你驾驶着一架 UFO,位于一个 n×nn\times n 的网格中。网格的点坐标为 (x,y)(x,y),其中 1≤x,y≤n1\le x,y\le n。部分点不可通行,以 * 表示;其余点可通行,以 . 表示。

最初你位于 (1,1)(1,1),希望尽快到达 (n,n)(n,n)。当你位于 (x,y)(x,y) 时,可以在一秒内传送到下列任意位置:

  • (x+1,y)(x+1,y)、(x,y+1)(x,y+1)、(x−1,y)(x-1,y)、(x,y−1)(x,y-1);
  • fi(x,y)f^i(x,y),其中 ii 是满足 0≤i≤k0\le i\le k 的任意整数。

这里 fif^i 定义为

$$f^i(x,y)=\begin{cases}(x,y),&i=0,\\f^{i-1}(y+1,x),&i>0.\end{cases}$$

如果传送的目的地在网格之外,或者目的地不可通行,则不能进行这次传送。一次 fif^i 传送只要求最终目的地合法,不需要逐次经过 f,f2,…,fi−1f,f^2,\ldots,f^{i-1} 所对应的位置。

求到达 (n,n)(n,n) 所需的最少时间。如果永远无法到达,输出 -1。

输入格式

第一行包含两个整数 n,kn,k,满足 1≤n,k≤50001\le n,k\le5000。

接下来 nn 行,每行 nn 个字符,表示网格。每个字符为 . 或 *。保证 (1,1)(1,1) 和 (n,n)(n,n) 都可通行。

输入仅包含一组数据。

输出格式

输出一行一个整数,表示最少时间;无法到达时输出 -1。

样例 1 输入

3 2
.*.
.*.
...

样例 1 输出

3

样例 2 输入

3 3
.*.
.*.
...

样例 2 输出

2