Wizard in Maze

题目描述

迷宫由 $H \times W$ 个方格组成——$H$ 行、$W$ 列。 从上数第 $i$ 行、从左数第 $j$ 列的方格 $(i,j)$ 若 $S_{ij}$ 为 # 则为墙，为 $.$ 则为道路。 魔法师位于 $(C_h,C_w)$。他可以进行以下两种移动：

Move A：走到与当前位置在垂直或水平方向上相邻的道路格子。 Move B：使用魔法将自己传送到以当前位置为中心的 $5\times 5$ 区域内的某个道路格子。

在任一情况下，他都不能走出迷宫。 到达 $(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

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

-1

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

0

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

2

提示

$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}$ and $S_{D_h D_w}$ are $.$. $(C_h,C_w) \neq (D_h,D_w)$例如，先走到 $(2,2)$ 然后使用一次魔法传到 $(4,4)$，仅需使用一次魔法。 注意他不能斜向行走。
他无法从那里移动。
不需要使用魔法。

标签: AtCoder|abc176D

来源

AtCoder|abc176D