本文共 3764 字，大约阅读时间需要 12 分钟。

走迷宫

今天讲一下 dfs/bfs 简单的应用——走迷宫。

dfs（深度优先搜索）

dfs 一般都是通过递归来完成（非递归也可以，但是有些麻烦），由于是递归，所以理解 dfs 的关键就在于解决“当下如何做”，而“下一步如何做”则与“当下如何做”是一样的。

下面给出 dfs 的基本模型：

void dfs(int step){
   	判断边界条件	尝试每一种可能 for( ; ; )	{
   		继续下一步 dfs(step + 1);	}	return;}

然后让我们正式开始走迷宫！

首先我们需要一张图来存放迷宫，我们使用一个二维数组来完成，迷宫中只有空地和障碍物，所以我们用 0 表示空地，1 表示障碍物， 我们需要来标记一个点是否已经走过，所以定义一个与存放迷宫一样的二维数组，0 表示为走，1 表示已走过，因为是地图，所以我们需要向 4 个方向延伸，再定义一个二维数组来寻找方向。 ok，准备工作已经完成，下面让我们来看一看代码：

#include
   
    using namespace std;//简单dfsint n,m;    //边界int start_x,start_y,end_x,end_y;  //起点，终点int x,y;    //坐标int G[51][51];        //地图int book[51][51];   //记录int Min = 99999999;//判断bool judge(int x, int y){
       if(x < 1 || x > n || y < 1 || y > m || G[x][y] == 1)        return false;    return true;}void dfs(int tx, int ty, int step){
       int next[4][2] = {
   {
   0,1},{
   1,0},{
   0,-1},{
   -1,0}};   //方向    //出口    if(tx == end_x && ty == end_y)    {
           //要最短路径        if(step < Min)            Min = step;        return;    }    //枚举4种走法（上下左右）    for(int i = 0; i < 4; i++)    {
           x = tx + next[i][0];        y = ty + next[i][1];                //判断是否满足条件        if(judge(x, y) && !book[x][y])        {
               book[x][y] = 1;         //标记该点已走过            dfs(x, y, step + 1);    //尝试下一个点            book[x][y] = 0;         //尝试结束，取消标记        }    }}int main(){
       cin >> n >> m;    for(int i = 1; i <= n; i++)        for(int j = 1; j <= m; j++)            cin >> G[i][j];        cin >> start_x >> start_y >> end_x >> end_y;    book[start_x][start_y] = 1; //标记起点已在路径中    dfs(start_x, start_y, 0);    cout << Min << endl;    return 0;}
   

注：标记完后一定要取消标记，因为是递归，而且 dfs 是一次要到底的，我们不能因为一次的搜索而影响到其它。

说实话，找最短路径还是 bfs 在行，所以赶快让我们来看一看它吧。

bfs（广度优先搜索）

与 dfs 一条路走到黑不同，bfs 是 “一层一层”往下进行的，它将每一次所能走到的点全都加入队列，直到到达目的地

（bfs 的标记不需要取消，因为 bfs 是将每一个点都入队，有可能不同的“上层”的点会到达相同的“下层”的点，所以这个标记就起了作用——不会把相同的点入队多次）。 下面我们来看一看代码：

#include
   
    using namespace std;//简单bfstypedef struct _node{
       int x;    int y;    int s;  //步数}node;int n,m;    //边界int start_x,start_y,end_x,end_y;  //起点，终点int x,y;    //坐标int G[51][51];        //地图int book[51][51];   //记录//判断bool judge(int x, int y){
       if(x < 1 || x > n || y < 1 || y > m || G[x][y] == 1)        return false;    return true;}void bfs(node start){
       queue
    
      q;    int next[4][2] = {
   {
   0,1},{
   1,0},{
   0,-1},{
   -1,0}};   //方向        //将起点入队    q.push(start);    //标记起点    book[start_x][start_y] = 1;    //队列不为空时循环    while(!q.empty())    {
           node now = q.front();        q.pop();                //出口        if(now.x == end_x && now.y == end_y)        {
               cout << now.s << endl;            return;        }        //枚举4种走法（上下左右）        for(int i = 0; i < 4; i++)        {
               x = now.x + next[i][0];            y = now.y + next[i][1];                        //判断是否满足条件            if(judge(x,y) && !book[x][y])            {
                   node New;                New.x = x;                New.y = y;                New.s = now.s + 1;                book[x][y] = 1;     //标记，每个点只需入队一次，所以不需要还原                q.push(New);        //入队            }        }    }    cout << "没有通路" << endl;}int main(){
       node start;    cin >> n >> m;    for(int i = 1; i <= n; i++)        for(int j = 1; j <= m; j++)            cin >> G[i][j];        cin >> start_x >> start_y >> end_x >> end_y;        start.x = start_x;    start.y = start_y;    start.s = 0;    bfs(start);    return 0;}
    
   

可以看到 dfs 与 bfs 在时间复杂度上是一样的，所以没有什么好坏之分，只是根据不同的情况来选择而已。dfs 更适合目标明确，以找到目标为主要目的的情况，而 bfs 则更适合寻找相对最优解的情况。

最后借用一下《大话数据结构》上的话：

这里还要再多说几句，对于深度和广度而言，已经不是简单的算法实现问题，完全可以上升到方法论的角度。你求学是博览群书，不求甚解，还是深钻细研，鞭策入里；你旅游是走马观花，蜻蜓点水，还是下马看花，深度体验；你交友是四海之内皆兄弟，还是人生得一知己足矣…其实都无对错之分，只视不同人的理解而有了不同的诠释。我个人觉得深度和广度是即矛盾又统一的两个方面，偏颇都不可取， 还望大家自己慢慢体会。

!@#$%^&*~

转载地址：http://snqwi.baihongyu.com/