J10 实践-9 逃离迷宫

题目描述

术士小喵被困在了密林迷宫中，庆幸的是小喵在之前的冒险中无意中获得了这个迷宫的地图。

密林迷宫由一个 $H\times W$ 的网格组成，每格的状态都在迷宫地图上标出，如果地图上的 $S_{i,j}$ 是 # ，表示在迷宫第 $i$ 行第 $j$ 列的位置是一堵墙，无法通行。如果地图上的 $S_{i,j}$ 是 . ，则对应位置是可以通行的路。

小喵现在所在的位置为 $(c_h,c_w)$ ，他需要到达在 $(d_h,d_w)$ 的传送门才能逃出这个密林迷宫，每次移动小喵可以选择以下两种方式中的一种：

• 步行：移动到与当前位置相邻的可通行的路上；
• 瞬移：通过瞬移术瞬移到以他当前位置为中心的 $5\times 5$ 范围内的可通行的路上。

由于密林迷宫的边缘被施加了强大的禁锢魔法，不管是通过步行还是瞬移小喵都无法走出迷宫的边界外。而且小喵所剩的魔力值也不多了，请问他最少使用多少次瞬移才能逃出这个密林迷宫？

输入格式

共 $H+2$ 行： 第一行两个整数 $H,W$ ，表示密林迷宫的行数和列数； 第二行两个整数 $c_h,c_w$ ，表示小喵起始位置的行列号； 第三行两个整数 $d_h,d_w$ ，表示传送门所在的行列号； 接下来的 $H$ 行每行一个长度为 $W$ 只由 # 或 . 组成的字符串，表示迷宫对应位置的情况。

输出格式

一行一个整数，输出小喵逃出迷宫所需的最少瞬移次数；若无法逃出迷宫，输出 -1 。

样例输入1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

样例输出1

1

样例1解析

步行到 $(2,2)$ 后瞬移至 $(4,4)$ ，使用一次瞬移逃出迷宫。

样例输入2

4 5
1 2
2 5
#.###
####.
#..##
#..##

样例输出2

2

数据范围

对于 $100 \%$ 的数据：$1\leq H,W\leq 10^3,1\leq c_h,d_h\leq H,1\leq c_w,d_w\leq W$ ，保证起点和终点都是 . 。