深度优先搜索DFS——迷宫解救

1.问题分析

 有一天同学B到独自一人到迷宫玩，方向感不好的B同学果不其然在迷宫中迷路，现在同学A要去解救B同学。

迷宫由n行m列的单元格组成，每个单元格要么是空地，要么是障碍物。任务就是帮助同学A找到一条从迷宫起点通往同学B的最短路径。注意，障碍物是不可以移走的，当然同学A也是不能走到地图之外。

2.算法设计 

（1）：首先我们可以用一个二维数组来存储这个迷宫，刚开始迷宫的入口在（1，1），而B同学的位置在（p，q），意思就是找到（1，1）到（p，q）的最短路径。我们可以先让同学A往右边走，直到走不通再回到原点。再往另一个方向尝试，我们规定一个顺序：右，下，左，上。

（2）：当找到同学B之后不意味着结束了， 因为这条路径不一定是最短的，需要返回到这些地方继续尝试往别的方向走，直到把所有可能都尝试一边，最后输出最短的一条路径。

（3）：我们用深度优先搜索来实现这个方法。我们来看看dfs()函数怎么实现：

首先我们需要三个参数，x坐标，y坐标，以及当前已经走过的步数step。

void dfs(int x,int y,int step)
{
    return;
}

（4）：如何判断同学A已经到达了同学B的位置呢：

void dfs(int x,int y,int step)
{
    if(x==p && y==q) //判断坐标是否相等
    {
        if(step<minn)
        {
            minn=step; //更新最小步数
        }
        return;
    }
    return;
}

（5）：如果没有找到B同学的位置，则找出下一步可以走的地方。有四个方向可以走，根据我们之前定义的方向，我们定义一个方向数组next：

    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; 
    //分别是向右走，向下走，向左走，向上走。

通过这个方向数组，使用循环就很容易获得下一步的坐标。这里将下一步的横坐标用tx，纵坐标用ty存储。

（6）：接下来我们要对下一个点（tx，ty）进行一些判断。包括是否越界、是否为障碍物，以及这个点是否已经在路径中（避免重复访问一个点）。需要用marked[tx][ty]来记录格子（tx，ty）是否已经在路中。

如果符合这些要求，就对这个但进行下一步的扩展，即dfs（tx，ty，step+1）。

    for (int 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(maze[tx][ty]==0 && marked[tx][ty]==0) //判断是否是障碍物或者是否已经在路径中
        {
            marked[tx][ty]=1;//说明这个点已经走过了
            dfs(tx,ty,step+1);
            marked[tx][ty]=0;//尝试结束，取消这个点的标记。
        }
    }

 

3.完整源代码 

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=11111;
int maze[N][N]; //地图数组
int marked[N][N];//标记数组
int n; //记录行数
int m;//记录列数
int p;//记录目标横坐标
int q;//记录目标纵坐标
int minn=9999999;

void dfs(int x,int y,int step)
{
    int tx;
    int ty;
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    //分别是向右走，向下走，向左走，向上走。

    if(x==p && y==q) //判断坐标是否相等
    {
        if(step<minn)
        {
            minn=step; //更新最小步数
        }
        return;
    }

    for (int 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(maze[tx][ty]==0 && marked[tx][ty]==0) //判断是否是障碍物或者是否已经在路径中
        {
            marked[tx][ty]=1;//说明这个点已经走过了
            dfs(tx,ty,step+1);
            marked[tx][ty]=0;//尝试结束，取消这个点的标记。
        }
    }
    return;
}

int main()
{
    int startx;
    int starty;
    cout << "请输入地图的大小：n和m" << endl;
    cin >> n>> m;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            cin >> maze[i][j];
        }
    }
    cout << "请输入起点的坐标和终点的坐标：" << endl;
    cin >> startx >> starty >> p >> q;
    marked[startx][starty]=1;//此时起点出发，说明已经在路径中
    dfs(startx,starty,0);
    cout << "A同学到达B同学位置的最短步数是：" << endl;
    cout << minn<< endl;
    return 0;
}

 

4.测试结果