题目描述

把一个n行m列的字符阵列看做一个迷宫，'S'表示迷宫的起点，'G'表示迷宫的终点，'#'表示不能通过的点，'.'表示可以通过的点。每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数，如果无解输出0。

输入格式

第一行两个正整数n、m，表示迷宫的规模为n行m列(0<m<100，0<n<100)；

接下来的n行：每行m个符合题意的字符。

输出格式

输出到终点的步数，如果无解输出0。

输入/输出样例

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

22

说明/提示

时间1000ms，内存256MiB