← 返回题单
题单练习 广度优先搜索
← 上一题 下一题 →

A5399 | Wizard in Maze

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有一个由 $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$。

输入格式

输入按以下格式从标准输入读入。

$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
C++ 编辑器
输入
输出