A5399. Wizard in Maze
编程题
普及/提高-
知识点
题目描述
有一个由 $H$ 行 $W$ 列组成的 $H\times W$ 的迷宫。
第 $i$ 行第 $j$ 列的格子 $(i,j)$，如果 $S_{ij}$ 为
有一位魔法使站在格子 $(C_h,C_w)$。魔法使可以通过以下两种方式移动：
- 移动A：步行到当前格子上下左右相邻的道路格子。
- 移动B：以当前格子为中心，在 $5\times 5$ 的范围内，通过魔法瞬移到任意道路格子。
无论哪种移动方式，都不能移动到迷宫外。
请问，最少需要使用多少次魔法瞬移才能到达格子 $(D_h,D_w)$？如果无法到达，则输出 $-1$。
第 $i$ 行第 $j$ 列的格子 $(i,j)$，如果 $S_{ij}$ 为
#，则为墙，否则为道路。有一位魔法使站在格子 $(C_h,C_w)$。魔法使可以通过以下两种方式移动：
- 移动A：步行到当前格子上下左右相邻的道路格子。
- 移动B：以当前格子为中心，在 $5\times 5$ 的范围内，通过魔法瞬移到任意道路格子。
无论哪种移动方式，都不能移动到迷宫外。
请问，最少需要使用多少次魔法瞬移才能到达格子 $(D_h,D_w)$？如果无法到达，则输出 $-1$。
输入格式
输入按以下格式从标准输入读入。
> $H$ $W$ $C_h$ $C_w$ $D_h$ $D_w$
> $S_{11}\ldots S_{1W}$
> $\vdots$
> $S_{H1}\ldots S_{HW}$
> $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
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
说明/提示
## 限制条件
- $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)$
## 样例解释 1
例如，可以先步行到 $(2,2)$，再从 $(2,2)$ 用魔法瞬移到 $(4,4)$，这样魔法瞬移的最小次数为 $1$。步行不能斜着走。
## 样例解释 2
无法从当前位置移动。
## 样例解释 3
不需要使用魔法瞬移。
- $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)$
## 样例解释 1
例如，可以先步行到 $(2,2)$，再从 $(2,2)$ 用魔法瞬移到 $(4,4)$，这样魔法瞬移的最小次数为 $1$。步行不能斜着走。
## 样例解释 2
无法从当前位置移动。
## 样例解释 3
不需要使用魔法瞬移。