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

r囧r小猫 2022-07-28 04:10 160阅读 0赞

问题及代码：

给出迷宫的图纸和初始终点位置，用DFS求最小步数。

#include <iostream>
    using namespace std;
    int n,m,p,q,MIN=99999999;
    int a[51][51],book[51][51];
    
    void dfs(int x,int y,int step)
    {
        int next[4][2]= {
       {0,1},{1,0},{0,-1},{-1,0}}; //顺时针：右下左上
        int tx,ty,k;
        if(x==p&&y==q)//是否到达
        {
            if(step<MIN)
                MIN=step;
            return;
        }
        //枚举四种方向的走法
        for(k=0; k<4; ++k)
        {
            tx=x+next[k][0];//计算坐标
            ty=y+next[k][1];
            if(tx<1||tx>n||ty<1||ty>m)//越界
                continue;
            if(a[tx][ty]==0&&book[tx][ty]==0)
            {
                book[tx][ty]=1;//标记走过
                dfs(tx,ty,step+1);
                book[tx][ty]=0;//尝试结束后取消标记
            }
        }
        return ;
    }
    
    int main()
    {
        int i,j,sx,sy;
        cin>>n>>m;//行、列
        for(i=1; i<=n; ++i)
            for(j=1; j<=m; ++j)
                cin>>a[i][j];//迷宫图
        cin>>sx>>sy>>p>>q;//迷宫入口和目标坐标
        book[sx][sx]=1;//从起点开始搜索，且起点已经在路程中
        dfs(sx,sy,0);//0表示初始步数
        cout<<MIN<<endl;
        return 0;
    }
    /*测试用例
    5 4
    0 0 1 0
    0 0 0 0
    0 0 1 0
    0 1 0 0
    0 0 0 1
    1 1 4 3
    */

运行结果：

![Center][]

阿，就是再回过头熟悉一下DFS算法：从一个方向走，走不通再回去尝试另外一个方向。

[Center]: /images/20220727/1bf0d863026a41078c5b91d49ec09b09.png

发表评论取消回复

表情：

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

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

相关阅读

相关深度优先搜索（DFS）

文章目录一、简介二、DFS的代码实现三、代码测试一、简介深度优先搜索是一种常见的图搜索算法，它可以用于寻找图中从起点到终点的路径或遍历

小灰灰/ 2024年03月22日 14:50/ 0 赞/ 97 阅读

相关深度优先搜索(DFS)

目录 1.基本思想 2.代码实现（C++） 3.性能分析 1.基本思想深度优先搜索(Depth-First-Search,DFS)的基本思想如

曾经终败给现在/ 2023年10月06日 16:51/ 0 赞/ 5 阅读

相关 DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节

缺乏、安全感/ 2022年10月30日 04:26/ 0 赞/ 193 阅读

相关 leetcode深度优先搜索（dfs）

1. 图像渲染有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像

深碍√TFBOYSˉ_/ 2022年09月04日 09:53/ 0 赞/ 186 阅读

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

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

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

相关 DFS-深度优先搜索—2

在这一篇博客：[http://blog.csdn.net/hacker\_zhidian/article/details/54773762][http_blog.csdn.ne

落日映苍穹つ/ 2022年07月11日 13:19/ 0 赞/ 211 阅读

相关走迷宫——深度优先搜索

Think: 1error ld returned 1 exit status错误可能原因： 1>函数调用与定义名称不匹配或定义名称与预定义名称不匹配 2>电脑多进

Dear 丶/ 2022年06月17日 06:46/ 0 赞/ 161 阅读

相关 DFS深度优先搜索模板

package test; public class DFS { final static int MAXN = 100;

亦凉/ 2022年06月03日 09:54/ 0 赞/ 194 阅读

相关迷宫--深度优先搜索

在迷宫中，有许多路障，如何在最快的时间，也就是路程最短啦,去解救一个人呢？ ![25752359.jpg][] 使用一个二维数组来存储这个迷宫，刚开始的

迈不过友情╰/ 2022年06月02日 06:49/ 0 赞/ 202 阅读

相关深度优先搜索（DFS）

DFS是相对于BFS的另一个中图搜索算法，其与BFS最大的不同在于它是深度优先，它会优先顺着一条路径走到底，一旦某个节点邻接的节点都被发现了，就会回溯到前面一个节点，直

以你之姓@/ 2022年05月15日 01:13/ 0 赞/ 251 阅读