分数: 400 点
问题陈述
迷宫由网格组成 H \times W 方块 - H 垂直, W 水平。
广场 i从顶部开始的第行和 j从左起第 - 列 - (i,j) - 是一堵墙,如果 S_{ij} is # 和一条路如果 S_{ij} is ..
里面有一个魔术师 (C_h,C_w)。他可以做以下两种动作:
- 移动A:走到与他当前所在的方格垂直或水平相邻的道路方格。
- 移动B:使用魔法将自己扭曲到道路方块中 5\times 5 以他当前所在广场为中心的区域。
无论哪种情况,他都无法走出迷宫。
他至少需要使用多少次魔法才能达到 (D_h, D_w)?
约束
- 1 \leq H,W \leq 10^3
- 1 \leq C_h,D_h \leq H
- 1 \leq C_w,D_w \leq W
- S_{ij} is
#or.. - S_{C_h C_w} 和 S_{D_h D_w} 是
.. - (C_h,C_w) \neq (D_h,D_w)
输入
输入由标准输入按以下格式给出:
H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}
输出
打印魔术师需要使用魔法的最少次数。如果他无法到达 (D_h,D_w),打印 -1 。
示例输入 1
4 4 1 1 4 4 ..#. ..#. .#.. .#..
示例输出 1
1
例如,步行至 (2,2) 然后使用魔法前往 (4,4),只需使用一次魔法就足够了。
请注意,他不能斜向行走。
示例输入 2
4 4 1 4 4 1 .##. #### #### .##.
示例输出 2
-1
他无法从那里移动。
示例输入 3
4 4 2 2 3 3 .... .... .... ....
示例输出 3
0
不需要使用魔法。
示例输入 4
4 5 1 2 2 5 #.### ####. #..## #..##
示例输出 4
2