RYIP在线题库
首 页   >   习题练习   >   提交
Problem1597--迷宫的最短路径

1597: 迷宫的最短路径

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

给定一个大小为 N*M 的迷宫。迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。测试数据保证从起点一定可以移动到终点。

【 Input 】

第一行包含两个正整数 N 和 M 分别表示迷宫的行数和列数,接下来的 N 行,每行包含 M 个字符描述迷宫的结构。用 '#'、'.'、'S' 和 'G'分别表示墙壁、通道、起点和终点。

【 Output 】

一个数,表示最小步数。

【 Sample Input 】

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
########.#
....#.....
.####.###.
....#...G#

【 Sample Output 】

22

【 Source/Category 】