Problem A: 迷宫最短路径
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:14
Solved:11
Description
给定一个 的迷宫,迷宫由以下元素组成:
. 表示可通行的路
# 表示墙(不可通行)
S 表示起点(只有一个)
E 表示终点(只有一个)
求从起点 S 到终点 E 的最短路径长度(即最少需要走多少步)。如果无法到达终点,输出 -1。
移动规则:每次可以向上下左右四个方向移动一步,不能斜着走,不能走出迷宫边界。
Input
第一行包含两个整数 和 ( ),表示迷宫的行数和列数。
接下来 行,每行 个字符,表示迷宫的布局。
保证迷宫中恰好有一个 S 和一个 E。
Output
输出一个整数,表示从 S 到 E 的最短路径长度。如果无法到达,输出 -1。
Sample Input Copy
4 4
S..#
#.#.
....
#..E
Sample Output Copy
6