题目描述

把一个n行m列的字符阵列看做一个迷宫，'S'表示迷宫的起点，'G'表示迷宫的终点，'#'表示不能通过的点，'.'表示可以通过的点。每一步可以向邻接的上下左右四格的通道移动，每个点只能通过一次。请你编写程序，求出给定的迷宫中，有多少种方法能走出迷宫。

输入格式

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

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

输出格式

输入通过迷宫的方法数，如果无解输出0。

输入/输出样例

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

0

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

2

说明/提示

时间1000ms，内存256MiB