#ABC007C. 迷宫最短路
迷宫最短路
题目描述
给定一个 的迷宫,字符 表示可通过的空地,字符 \texttt{`#'} 表示墙壁。
从 出发,每步可移动到上下左右相邻的空地,不能进入墙壁。求到达 的最少步数。
迷宫边界全部是墙壁,起点和终点不同,且保证二者都是空地并互相可达。
输入格式
第一行输入两个整数 。
第二行输入两个整数 $x_s,y_s\left(1\leqq x_s\leqq n;\ 1\leqq y_s\leqq m\right)$,代表起点的行、列。
第三行输入两个整数 $x_t,y_t\left(1\leqq x_t\leqq n;\ 1\leqq y_t\leqq m\right)$,代表终点的行、列。
此后 行,每行输入一个长度为 、仅含 和 \texttt{`#'} 的字符串。保证满足题目中的边界和可达性条件。
输出格式
输出一个整数,代表从起点到终点的最少步数。
测试样例
7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########
11
样例 1 解释
虽然起点与终点的曼哈顿距离只有 ,中间墙壁迫使路径绕行。可以走 $(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)$,共 步。
5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########
10
50 50
2 2
49 49
##################################################
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
#................................................#
##################################################
94
解题提示
可以采用广度优先搜索。先把起点距离设为 并入队,每次从先进先出队列取出一个格子,将未访问的相邻空地的距离设为当前距离加 ,再加入队尾。这样按距离从小到大扩展,首次到达某格时即得到最短距离。原题已有该算法提示,此处保留。