#ABC007C. 迷宫最短路

迷宫最短路

题目描述

\hspace{15pt}给定一个 n×mn\times m 的迷宫,字符 ‘.’\texttt{`.'} 表示可通过的空地,字符 \texttt{`#'} 表示墙壁。

\hspace{15pt}从 (xs,ys)(x_s,y_s) 出发,每步可移动到上下左右相邻的空地,不能进入墙壁。求到达 (xt,yt)(x_t,y_t) 的最少步数。

\hspace{15pt}迷宫边界全部是墙壁,起点和终点不同,且保证二者都是空地并互相可达。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦50)n,m\left(1\leqq n,m\leqq50\right)。

\hspace{15pt}第二行输入两个整数 $x_s,y_s\left(1\leqq x_s\leqq n;\ 1\leqq y_s\leqq m\right)$,代表起点的行、列。

\hspace{15pt}第三行输入两个整数 $x_t,y_t\left(1\leqq x_t\leqq n;\ 1\leqq y_t\leqq m\right)$,代表终点的行、列。

\hspace{15pt}此后 nn 行,每行输入一个长度为 mm、仅含 ‘.’\texttt{`.'} 和 \texttt{`#'} 的字符串。保证满足题目中的边界和可达性条件。

输出格式

\hspace{15pt}输出一个整数,代表从起点到终点的最少步数。

测试样例

7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########
11

样例 1 解释

\hspace{15pt}虽然起点与终点的曼哈顿距离只有 55,中间墙壁迫使路径绕行。可以走 $(2,2)\to(3,2)\to(4,2)\to(4,3)\to(5,3)\to(6,3)\to(6,4)\to(6,5)\to(6,6)\to(5,6)\to(4,6)\to(4,5)$,共 1111 步。

5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########
10
50 50
2 2
49 49
##################################################
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
##################################################
94

解题提示

\hspace{15pt}可以采用广度优先搜索。先把起点距离设为 00 并入队,每次从先进先出队列取出一个格子,将未访问的相邻空地的距离设为当前距离加 11,再加入队尾。这样按距离从小到大扩展,首次到达某格时即得到最短距离。原题已有该算法提示,此处保留。