D - 迷宫之巫师

得分：400分

问题描述

迷宫由一个 $H \times W$ 的方格组成，其中有 $H$ 个垂直方向，$W$ 个水平方向的方格。

如果第 $i$ 行，第 $j$ 列的方格为 $S_{ij}$ 是 #，则表示墙壁；如果 $S_{ij}$ 是 .，则表示道路。

巫师当前在 $(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}$ 是 # 或者 .
• $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。

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

1

例如，巫师可以走到 $(2,2)$，然后通过使用魔法移动到 $(4,4)$，只需要一次魔法的使用。

请注意他不能对角行走。

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

-1

他无法从起点移动。

4 4
2 2
3 3
....
....
....
....

0

不需要使用魔法。

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

2