迷宫（DFS）

青旅半醒 2022-05-25 02:37 175阅读 0赞

Problem 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

Sample Output：

1  
0

4

思路：这道题用深搜+回溯，但要注意时间超限的问题。

My DaiMa：

#include <stdio.h>
    #include <string.h>
    int a[8][8];
    int count;
    int m,n;
    void dfs(int i,int j)
    {
        if(i < 0 || j < 0 || i >= n || j >= m || a[i][j])
            return ;
        if(i == n-1 && j == m-1)
        {
            count ++ ;
            return ;
        }
        a[i][j] = 1;
        dfs(i - 1,j);
        dfs(i + 1,j);
        dfs(i,j - 1);
        dfs(i,j + 1);
        a[i][j] = 0;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T -- )
        {
            int i,j;
            count = 0;
            memset(a,0,sizeof(a));
            scanf("%d%d",&n,&m);
            for(i = 0; i < n; i ++ )
                for(j = 0; j < m; j ++ )
                    scanf("%d",&a[i][j]);
            dfs(0,0);
            printf("%d\n",count);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关 DFS之连通性模型 AcWing 1112. 迷宫

DFS之连通性模型 AcWing 1112. 迷宫原题链接 [AcWing 1112. 迷宫][AcWing 1112.] 算法标签 DFS 思路

电玩女神/ 2024年04月07日 10:19/ 0 赞/ 71 阅读

相关 DFS深度优先刷题【1215：迷宫】

[http://ybt.ssoier.cn:8088/problem\_show.php?pid=1215][http_ybt.ssoier.cn_8088_problem_s

╰+攻爆jí腚メ/ 2022年12月21日 02:29/ 0 赞/ 117 阅读

相关 5-13 地下迷宫探索 (30分)——DFS

sthink: 1开学后一直没有写博客，感觉明显没有假期时候的学习效率，不管是专业课还是别的课程，感觉自己很难达到第一学期的激情与效率，相对于别的同学感觉自己变得迷茫了，不

男娘i/ 2022年09月27日 06:23/ 0 赞/ 147 阅读

相关 poj 3984 迷宫问题【BFS && DFS】【简单】

迷宫问题 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

布满荆棘的人生/ 2022年08月10日 09:16/ 0 赞/ 190 阅读

相关 poj 3984 迷宫问题【dfs】

迷宫问题 Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0

￡神魔★判官ぃ/ 2022年08月09日 01:48/ 0 赞/ 158 阅读

相关深度优先搜索DFS（迷宫问题）

问题及代码：给出迷宫的图纸和初始终点位置，用DFS求最小步数。 include <iostream> using namespace std; i

r囧r小猫/ 2022年07月28日 04:10/ 0 赞/ 155 阅读

相关迷宫问题 DFS写法 BFS写法

定义一个二维数组： int maze\[5\]\[5\] = \{ 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0

红太狼/ 2022年06月18日 09:56/ 0 赞/ 213 阅读

相关迷宫（DFS）

Problem Description：一个由 n \ m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是

青旅半醒/ 2022年05月25日 02:37/ 0 赞/ 176 阅读

相关「迷宫问题」队列+BFS与栈+DFS分别求解

1 迷宫问题一个迷宫如图所示，他有一个入口和一个出口，其中白色单元表示通路，黑色单元表示不通路。试寻找一条从入口到出口的路径，每一部只能从一个白色单元走到相邻的白色单元

绝地灬酷狼/ 2022年05月24日 03:24/ 0 赞/ 216 阅读

相关 PHP实现迷宫最短路径查找（DFS）

条件： a. 一个M\N的二维的迷宫，用一个二维数组Matrix表示 b. 无法到达的地方标记为1，可以到达的地方标记为0 c. 从任何一个位置Matrix\[i\]\[

布满荆棘的人生/ 2022年05月17日 11:50/ 0 赞/ 156 阅读