走迷宫
Time Limit: 1000MS Memory limit: 65536K
题目描述
一个由n * m 个格子组成的迷宫，起点是(1, 1)， 终点是(n, m)，每次可以向上下左右四个方向任意走一步，并且有些格子是不能走动，求从起点到终点经过每个格子至多一次的走法数。
输入
第一行一个整数T 表示有T 组测试数据。(T <= 110)
对于每组测试数据:
第一行两个整数n, m，表示迷宫有n * m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行，每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走，否则是1 表示这个格子不能走，输入保证起点和终点都是都是可以走的。
任意两组测试数据间用一个空行分开。
输出
对于每组测试数据，输出一个整数R，表示有R 种走法。
示例输入
3 2 2 0 1 0 0 2 2 0 1 1 0 2 3 0 0 0 0 0 0
示例输出
1 0 4
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define maxn 10
5 int map[maxn][maxn],vis[maxn][maxn],n,m,k;
6 void BFS(int u,int v)
7 {
8 int x,y;
9 int a[]= {0,0,-1,1},b[]= {-1,1,0,0};
10 for(int i=0; i<4; i++)
11 {
12 x=u+a[i];
13 y=v+b[i];
14 if(x==n && y==m)
15 k++;
16 else if(x<=n && x>0 && y<=m && y>0)
17 {
18 if(!map[x][y] && !vis[x][y])
19 {
20 vis[x][y]=1;
21 BFS(x,y);
22 }
23 }
24 }
25 vis[u][v]=0;//vis[u][v]的值在上面的循环中可能会改变，所以要清零。
26 }
27 int main()
28 {
29 int T;
30 scanf("%d",&T);
31 while(T--)
32 {
33 k=0;
34 int i,j;
35 memset(map,0,sizeof(map));
36 memset(vis,0,sizeof(vis));
37 scanf("%d%d",&n,&m);
38 for(i=1; i<=n; i++)
39 for( j=1; j<=m; j++)
40 scanf("%d",&map[i][j]);
41 vis[1][1]=1;
42 BFS(1,1);
43 //验证输出
44 /* for(i=1;i<=n;i++)
45 {
46 for(j=1;j<=m;j++)
47 printf("%d ",vis[i][j]);
48 printf("
");
49 }*/
50 printf("%d
",k);
51 }
52 return 0;
53 }