问题 F: 迷宫

问题 F: 迷宫

时间限制: 1 Sec  内存限制: 128 MB
提交: 170  解决: 84
[提交][状态][讨论版][命题人:]

题目描述

小明来到了一个大小为N*M的迷宫,迷宫由通道和墙壁组成,小明每一步可以向邻接的上下左右四格的通道移动。请你帮小明算出从起点到终点所需的最小步数。假设这个迷宫一定可以从起点移动到终点。
迷宫的表示方法为:'#'表示墙壁,'.'表示通道,'S'表示起点,'G'表示终点。

输入

第一行包含两个整数N M,定义如题所述。N,M≤100。

输出

到达终点的最短步数。

样例输入

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

样例输出

22

提示

[提交][状态]