啊哈！算法—深度优先搜索DFS—解救小哈

拼搏现实的明天。 2022-08-21 13:57 165阅读 0赞

小哈去玩迷宫，结果迷路了，小哼去救小哈。迷宫由n行m列的单元格组成（n和m都小于等于50），每个单元格要么是空地，要么是障碍物。

问题：帮小哼找到一条从迷宫的起点通往小哈所在位置的最短路径。（注意：障碍物不能走，小哼也不能走出迷宫外）

输入例如：

0 0 1 0  
0 0 0 0  
0 0 1 0  
0 1 0 0  
0 0 0 1  
1 1 4 3  
输出：

#include <iostream>
    using namespace std;
    int n,m,p,q,mmin=999999;
    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<mmin)
                mmin=step;
            return;
        }
        for(k=0; k<=3; 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,startx,starty;
        cin>>n>>m;          //输入n行m列，并读入各点
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
                cin>>a[i][j];
        cin>>startx>>starty>>p>>q;      //读入起点和终点坐标
        //从起点开始搜索
        book[startx][starty]=1;       //标志起点已经在路径中，防止后面重复走
        dfs(startx,starty,0);      //参数分别为起点坐标x，起点坐标y，初始步数0
        cout<<endl<<"最短路径为："<<mmin<<endl;     //输出最短步数
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220724/7e997430b253445baa80719c8b5cf0b3.png