给定一个 的网格迷宫,S 表示起点,E 表示终点,. 表示可以通行的空地,# 表示不可通行的墙壁。
S
E
.
#
每次只能向上下左右四个正方向移动一格。请你求出从起点走到终点的最短步数。如果无法到达终点,请输出 -1。
-1
第一行包含两个整数 和 ()。
接下来的 行,每行包含一个长度为 的字符串,表示迷宫地图。
保证起点 S 和终点 E 在地图中各自恰好出现一次。
输出一个整数,表示最短步数。如果无法到达,输出 -1。
3 4 S..# .#.. ...E
5
一条可行的最短路径为:
起点 (1,1) (1,2) (1,3) (2,3) (3,3) 终点 (3,4)。
(1,1)
(1,2)
(1,3)
(2,3)
(3,3)
(3,4)
共经过 5 步到达终点。