题目描述
一个由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 map[
101][
101],vis[
101][
101];
4 int n,m,ans;
5 void dfs(
int x,
int y)
6 {
7 if(vis[x][y] ||
map[x][y])
8 return;
9 if(x == n && y ==
m)
10 {
11 ans++
;
12 return;
13 }
14 vis[x][y] =
1;
15 dfs(x-
1,y);dfs(x+
1,y);
16 dfs(x,y-
1);dfs(x,y+
1);
17 vis[x][y] =
0;
18 }
19 int main()
20 {
21 int t;
22 scanf(
"%d",&
t);
23 while(t--
)
24 {
25 scanf(
"%d %d",&n,&
m);
26 memset(vis,
0,
sizeof(vis));
27 for(
int i =
1; i <= n; i++
)
28 for(
int j =
1; j <= m; j++
)
29 scanf(
"%d",&
map[i][j]);
30 for(
int i =
0; i <= n+
1; i++
)
31 {
32 map[i][
0] =
1;
33 map[i][m+
1] =
1;
34 }
35 for(
int j =
0; j <= m+
1; j++
)
36 {
37 map[
0][j] =
1;
38 map[n+
1][j] =
1;
39 }
40 ans =
0;
41 dfs(
1,
1);
42 printf(
"%d\n",ans);
43 }
44 return 0;
45 }
View Code
转载于:https://www.cnblogs.com/LK1994/p/3151819.html
相关资源：走迷宫C语言
