给一个 n行m列的2维的迷宫，‘S’表示迷宫的起点，‘T’表示迷宫的终点，’#‘表示不能通过的点，’.’ 表示可以通过的点。你需要从’S’出发走到’T’，每次只能上下左右走动，并且只能进入能通过的点，每个点只能通过一次。现在要求你求出有多少种通过迷宫的的方案。
输入格式 第一行输入n,m(1≤n,m≤10)表示迷宫大小。 接下来输入 nn 行字符串表示迷宫。
输出格式 输入通过迷宫的方法数。
样例输入1 2 3 S.# ..T 样例输出1 2 样例输入2 3 3 S.. .#. ..T 样例输出2 2 #include <bits/stdc++.h> using namespace std; char a[10][11]; int b[10][10] = {0}; int way, S_x, S_y, T_x, T_y, n, m; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void solve(int x, int y) { if (x != T_x || y != T_y) { for (int k = 0; k < 4; k++) { if (a[x + dx[k]][y + dy[k]] != '#' && b[x + dx[k]][y + dy[k]] == 0 && x + dx[k] >= 0 && x + dx[k] <= n - 1 && y + dy[k] >= 0 && y + dy[k] <= m - 1) { b[x + dx[k]][y + dy[k]] = 1; solve(x + dx[k], y + dy[k]); b[x + dx[k]][y + dy[k]] = 0; } } } else way++; } int main() { int i, j; scanf("%d%d", &n, &m); getchar(); for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { scanf("%c", &a[i][j]); if (a[i][j] == 'S') { S_x = i; S_y = j; } if (a[i][j] == 'T') { T_x = i; T_y = j; } } getchar(); } b[S_x][S_y] = 1; solve(S_x, S_y); printf("%d", way); return 0; }
