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

逃离我推掉我的手 2022-12-16 03:55 115阅读 0赞

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

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  
3  
2 2  
0 1  
0 0  
2 2  
0 1  
1 0  
2 3  
0 0 0  
0 0 0  
Output  
1  
0  
4

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int  map[101][101], vis[101][101];//数组不能开太大，不然会超时（memset）
    int n, m, step;
    void dfs(int x, int y)
    {
        
    	if (x<1 || y<1 || x>n || y>m || map[x][y] == 1)//超界就结束，0可以走，1不能走
    		return;
    	if (x == n && y == m)//到达一次终点就算一次方法（step++）
    	{
        
    		step++;
    		return;
    	}
    	if (vis[x][y]==0 && map[x][y]==0)//如果这个点还没有被访问过，且路是通的
    	{
        
    		vis[x][y] = 1;
    		dfs(x + 1, y);
    		dfs(x - 1, y);
    		dfs(x, y + 1);
    		dfs(x, y - 1);
    		vis[x][y] = 0;
    	}//在上面先标记成这个点已经被访问过，防止在一条路的寻找中重复经过同一个点，然后dfs递归找下一步的路。找完之后再返回原状态，继续寻找下一条新路
    }
    int main()
    {
        
    	int t,i,j;
    	scanf("%d", &t);
    	while (t--)
    	{
        
    		step = 0;
    		memset(map, 0, sizeof(map));
    		memset(vis, 0, sizeof(vis));
    		scanf("%d %d", &n, &m);
    		for (i = 1; i <= n; i++)
    		{
        
    			for (j = 1; j <= m; j++)
    			{
        
    				scanf("%d", &map[i][j]);
    			}
    		}
    		step = 0;
    		dfs(1, 1);
    		printf("%d\n", step);
    	}
    }