走迷宫
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 int count=
0;
4 int vis[
100][
100], map[
100][
100];
5 int n,m;
6 void dfs(
int i,
int j)
7 {
8 if(vis[i][j]==
1||map[i][j]==
1)
return ;
9 if(i==n&&j==
m)
10 {
11 count++
;
12 return;
13 }
14 vis[i][j]=
1; 注意标记访问 要放在return 之后。
15 dfs(i-
1,j);
16 dfs(i+
1,j);
17 dfs(i,j-
1);
18 dfs(i,j+
1);
19 vis[i][j] =
0;
20 }
21 int main ()
22 {
23 int t,i,j;
24
25
26
27 scanf(
"%d",&
t);
28 while(t--
)
29 {
30 count =
0;
31 memset(map,
0,
sizeof(map));
32 memset(vis,
0,
sizeof(vis));
33 scanf(
"%d %d",&n,&
m);
34 for(i=
0;i<=n+
1;i++
)
35 for(j=
0;j<=m+
1;j++
)
36 {
37 if(i==
0 || i==n+
1 || j==
0 || j==m+
1)
38 map[i][j]=
1; 迷宫外加一道墙，。
39 else scanf(
"%d",&
map[i][j]);
40 }
41 dfs(
1,
1);
42 printf(
"%d\n",count);
43 }
44 return 0;
45 }
46
47
48
转载于:https://www.cnblogs.com/LK1994/archive/2013/03/23/2977543.html
相关资源：JAVA上百实例源码以及开源项目
