#P18711. Teleport
Teleport
Teleport
你驾驶着一架 UFO,位于一个 的网格中。网格的点坐标为 ,其中 。部分点不可通行,以 * 表示;其余点可通行,以 . 表示。
最初你位于 ,希望尽快到达 。当你位于 时,可以在一秒内传送到下列任意位置:
- 、、、;
- ,其中 是满足 的任意整数。
这里 定义为
$$f^i(x,y)=\begin{cases}(x,y),&i=0,\\f^{i-1}(y+1,x),&i>0.\end{cases}$$如果传送的目的地在网格之外,或者目的地不可通行,则不能进行这次传送。一次 传送只要求最终目的地合法,不需要逐次经过 所对应的位置。
求到达 所需的最少时间。如果永远无法到达,输出 -1。
输入格式
第一行包含两个整数 ,满足 。
接下来 行,每行 个字符,表示网格。每个字符为 . 或 *。保证 和 都可通行。
输入仅包含一组数据。
输出格式
输出一行一个整数,表示最少时间;无法到达时输出 -1。
样例 1 输入
3 2
.*.
.*.
...
样例 1 输出
3
样例 2 输入
3 3
.*.
.*.
...
样例 2 输出
2