数据结构实验之栈与队列十：走迷宫

Description

一个由n * m 个格子组成的迷宫，起点是(1, 1)，终点是(n, m)，每次可以向上下左右四个方向任意走一步，并且有些格子是不能走动，求从起点到终点经过每个格子至多一次的走法数。

Input

第一行一个整数T 表示有T 组测试数据。(T <= 110)

对于每组测试数据:

第一行两个整数n, m，表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行，每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走，否则是1 表示这个格子不能走，输入保证起点和终点都是都是可以走的。

任意两组测试数据间用一个空行分开。

Output

对于每组测试数据，输出一个整数R，表示有R 种走法。

Sample

Input

Output

1
0
4

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 int a[10][10], flag[10][10];
 5 int k, n, m;
 6 void dfs(int x, int y)
 7 {
 8     int t[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
 9     int tx, ty;
10     if(x == n && y == m)
11     {
12         k++;
13         return;
14     }
15     for(int i = 0; i <= 3; i++)
16     {
17         tx = x + t[i][0];
18         ty = y + t[i][1];
19         if(tx < 1 || tx > n || ty <1 || ty > m)
20             continue;
21         if(flag[tx][ty] == 0 && a[tx][ty] == 0)
22         {
23             flag[tx][ty] = 1;
24             dfs(tx, ty);
25             flag[tx][ty] = 0;
26         }
27     }
28     return;
29 }
30 int main()
31 {
32     int i, j, t;
33     scanf("%d", &t);
34     while(t--)
35     {
36         k = 0;
37 //memset(a, 0, sizeof(a));
38         scanf("%d%d", &n, &m);
39         for(i = 1; i <= n; i++)
40         {
41             for(j = 1; j <= m; j++)
42             {
43                 scanf("%d", &a[i][j]);
44             }
45         }
46         flag[1][1] = 1;
47         dfs(1, 1);
48         printf("%d
", k);
49     }
50     return 0;
51 }