A5379. 幅優先探索
编程题
普及/提高-
知识点
题目描述
一个大小为 $n\times m$ 的迷宫，你可以往上下左右任意方向移动 $1$ 步，求最少需要多少步才能走出迷宫。
迷宫中
迷宫中
. 表示空地，# 表示墙壁，移动中只能穿过空地，不能穿墙。输入格式
第 $1$ 行 $2$ 个正整数 $n, m$，表示迷宫有 $n$ 行 $m$ 列；
第 $2$ 行 $2$ 个正整数 $sy,sx$，表示起点坐标 $(sy,sx)$;
第 $3$ 行 $2$ 个正整数 $gy,gx$，表示终点坐标 $(gy,gx)$;
第 $4$ 至 $n+1$ 行，表示迷宫的俯视图
第 $2$ 行 $2$ 个正整数 $sy,sx$，表示起点坐标 $(sy,sx)$;
第 $3$ 行 $2$ 个正整数 $gy,gx$，表示终点坐标 $(gy,gx)$;
第 $4$ 至 $n+1$ 行，表示迷宫的俯视图
输出格式
输出最少需要多少步才能走出迷宫。（题目保证有解）
输入输出样例
输入 #1
7 8 2 2 4 5 ######## #......# #.###### #..#...# #..##..# ##.....# ########
输出 #1
11
输入 #2
5 8 2 2 2 4 ######## #.#....# #.###..# #......# ########
输出 #2
10
输入 #3
50 50 2 2 49 49 ################################################## #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# ##################################################
输出 #3
94
说明/提示
对于 $100\%$ 的数据，$1\le n, m\le50$，$sy, gy\le n$，$sx,gx\le m$。