题目描述

把一个n行m列的字符阵列看做一个迷宫，'S'表示迷宫的起点，'G'表示迷宫的终点，'#'表示不能通过的点，'.'表示可以通过的点。每一步可以向邻接四格的通道移动（按照左、上、右、下的优先顺序），每个点只能通过一次。设左上角的格子坐标为(0,0)，右下角的坐标为(n-1,m-1)。输出通过迷宫的所有方法。

输入格式

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

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

输出格式

若干行，每行一种方案，按顺序输出从起点到终点的位置坐标，每个点包括用小括号括起来的x坐标和y坐标，中间用逗号隔开。

相邻两个坐标之间有一个空格，如果无解输出0。

输入/输出样例

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

(0,0) (0,1) (0,2) (0,3) (1,3) (2,3)
(0,0) (1,0) (1,1) (0,1) (0,2) (0,3) (1,3) (2,3)

说明/提示

时间1000ms，内存256MiB