深度优先搜索解决迷宫问题（最小步数求解）_深度优先算法迷宫问题

1.深度优先搜索解决迷宫问题

迷宫问题是一个经典的图搜索问题，其中迷宫由一系列的单元格组成，有些单元格之间可以相互通行，有些则不行。玩家的目标是从迷宫的起点出发，通过一系列合法的移动，最终到达迷宫的终点。深度优先搜索（DFS）是解决迷宫问题的一种有效算法。

2.深度优先搜索的基本原理

深度优先搜索是一种用于遍历或搜索树或图的算法。在迷宫问题中，我们可以将迷宫看作一个图，其中每个单元格都是一个节点，可通行的单元格之间用边相连。DFS会从起点开始，尽可能深地搜索迷宫的分支，直到找到终点或者搜索到尽头（即死胡同）为止。如果当前分支搜索完毕仍然没有找到终点，DFS会回溯到上一个节点，继续搜索下一条分支。

3.DFS解决迷宫问题的步骤

1. 初始化：

   • 创建一个迷宫地图，表示每个单元格是否可以通行。
   • 设置起点和终点。

2. 开始搜索：标记起点为已访问。

3. 深度搜索：

   • 从栈中弹出一个节点。
   • 检查该节点是否为终点。如果是，则找到解决方案，结束搜索。
   • 如果不是终点，则遍历该节点的所有邻居节点（即可以通行的单元格）。对于每个未访问过的邻居节点，执行以下操作：
     • 继续深度搜索。
     • 标记为已访问。
     • 如果所有邻居节点都已访问过，或者没有合法的邻居节点（即死胡同），则回溯到上一个节点。

4. 回溯：

   • 当从死胡同回溯到上一个节点时，继续从该节点搜索其他未访问过的分支。
   • 如果所有分支都已搜索完毕，且没有找到终点，则结束搜索。

5. 输出结果：

   • 如果找到终点，则可以输出搜索路径或解决方案。
   • 如果没有找到终点，则说明迷宫无解或起点和终点不可达。

4.DFS解决迷宫问题的优势与不足

优势：

• DFS可以很容易地实现，且代码相对简单。
• 对于规模较小的迷宫问题，DFS通常能够较快地找到解决方案（如果存在的话）。

不足：

• DFS可能会在不必要的分支上浪费大量时间，导致效率不高。
• 对于规模较大的迷宫问题，DFS可能需要很长时间才能找到解决方案，甚至可能根本找不到。
• DFS的空间复杂度较高，因为它需要存储搜索路径和已访问的节点信息。

5.结论

深度优先搜索是解决迷宫问题的一种经典算法，它可以有效地找到从起点到终点的路径（如果存在的话）。然而，对于复杂的迷宫问题，可能需要结合其他算法或优化技术来提高搜索效率。在实际应用中，我们还需要根据具体问题的规模和特点来选择合适的算法。

6.代码实现

#include<stdio.h>
#include<iostream>
using namespace std;
int n,m,p,q,minstep=9999;//n*m的迷宫,终点（p，q）
int a[51][51],book[51][51];
int t[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//右下左上向量
 
void dfs(int x,int y,int step){
    int tx,ty;
    if (x==p&&y==q)
    {
        if(step<minstep)minstep=step;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        tx=x+t[i][0];
        ty=y+t[i][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(){
    cin>>n>>m;
    for (int i = 1; i <=n; i++)for (int j = 1; j <=m; j++)cin>>a[i][j];
    int startx,starty;
    cout<<"start:";cin>>startx>>starty;
    cout<<"final:";cin>>p>>q;
    book[startx][starty]=1;
    dfs(startx,starty,0);
    cout<<"minstep:"<<minstep;
    return 0;
}

相似的另一种写法

#include<iostream>
#include<string.h>
#define MAX 100
using namespace std;
int a[MAX+1][MAX+1],book[MAX+1][MAX+1];
int nextxy[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int n,m,minstep=MAX*MAX;
int ex,ey;
void dfs(int x,int y,int step){
   if (x==ex&&y==ey)
   {
    if(step<minstep)minstep=step;
    return;
   }
   int tx,ty;
   for(int i=0;i<4;i++){
    tx=x+nextxy[i][0];
    ty=y+nextxy[i][1];
    if(tx<1||tx>n||ty<1||ty>m||book[tx][ty]==1||a[tx][ty]==1)continue;
    book[tx][ty]=1;
    dfs(tx,ty,step+1);
    book[tx][ty]=0;
   }
   
}
 
int main(){
    cin>>n>>m;//n*m
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)cin>>a[i][j];
    int sx,sy;
    cin>>sx>>sy;
    cin>>ex>>ey;
    book[sx][sy]=1;
    dfs(sx,sy,0);
 
    cout<<"minstep="<<minstep<<endl;
    return 0;
}

7.注意事项

1.注意坐标和判断条件

数组下标起点为0，本文舍弃了【0】，从【1】开始，即【1】【1】为坐标起点。

判断条件为：

if (tx<1||tx>n||ty<1||ty>m)continue;//检查越界
        if (a[tx][ty]==0&&book[tx][ty]==0)//未走过且非障碍

或者可以写成

if(tx<1||tx>n||ty<1||ty>m||book[tx][ty]==1||a[tx][ty]==1)continue;