题目描述

把一个n行m列的字符阵列看做一个迷宫，'S'表示迷宫的起点，'G'表示迷宫的终点，'#'表示不能通过的点，'.'表示可以通过的点。每一步可以向邻接的上下左右四格的通道移动。输出从起点到终点所需的最短路径，如果有不止一条路径最短，按照左、上、右、下的优先顺序。如果无解输出0。

左上角的坐标是(1,1)，右下角的坐标是(n,m)。

输入格式

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

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

输出若干个最短路径上的点的坐标，由一对圆括号，两个整数和一个逗号组成，如(x,y)。相邻两个坐标之间有一个空格，如果无解输出0。

3 4
.S..
###.
..G.

(1,2) (1,3) (1,4) (2,4) (3,4) (3,3)

时间1000ms，内存256MiB