【AcWing刷题】蓝桥杯专题突破-广度优先搜索-bfs（11）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【AcWing刷题】蓝桥杯专题突破-广度优先搜索-bfs（11）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面：

题目：844. 走迷宫 - AcWing题库

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：844. 走迷宫 - AcWing题库

题目描述：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

输入格式：

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（00 或 11），表示完整的二维数组迷宫。

输出格式：

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围：

1 ≤ n, m ≤ 100

输入样例：

输出样例：

解题思路：

今天，我开始学习广度优先搜索，

如果说深度优先搜索是一直往下搜，触底反弹回溯，再继续搜索出所有情况，

那么广度优先是一层一层的搜索，

简单来说就是就是运用二叉树层序遍历的思想进行搜索，

就比如这道题，走迷宫，我们也可以用深度优先搜索去做，

但是题目要求的数据范围比较大，深度优先会超出时间限制，

所以这个时候就要用到广度优先搜索，

接下来是具体思路：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

我们需要从左上角到右下角，

找出他们的最短路径和，

运用广度优先的思想：

开始搜索：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

继续往下搜索：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

红色的数字1，表示的是该坐标与起点距离是1，

层层记录距离，就能返回最短路径和，

继续搜索：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

以此类推：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

我们就搜索到了最短的路径和，

那么这是怎么实现的呢？

就是利用队列先进先出的特性，

往下遍历的时候，将下一层的数据全部入队：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

然后就让该坐标出队，并将下一层入队：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

继续出队，然后入队：

蓝桥杯搜索题,蓝桥杯备赛,蓝桥杯,宽度优先,算法

就能够达成我们广度搜索的条件往下搜索，

下面是代码实现：

代码：

//包好常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

//用来存坐标
typedef pair<int, int> PII;

const int N = 110;

int n, m;

//队列
queue<PII> q;

//用来读入地图
int g[N][N];

//用来记录地图状态和层数（离初始位置的距离）
int dist[N][N];

//坐标偏移量
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int bfs(int x, int y)
{
    //先把状态都置位-1
    memset(dist, -1, sizeof(dist));
    q.push({x, y});
    
    //起点
    dist[x][y] = 0;
    
    //如果队列不为空，就一直出队搜索
    while(!q.empty())
    {
        //记录队头
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            //上下左右搜索
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            
            //控制边界
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(g[a][b] != 0) continue;
            
            //如果走过，就不搜索了
            if(dist[a][b] > 0) continue;
            
            //入队
            q.push({a, b});
            
            //记录的路径和+1
            dist[a][b] = dist[t.first][t.second] + 1;
        }
    }
    //返回终点的路径和
    return dist[n][m];
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d", &g[i][j]);
        }
    }
    
    int res = bfs(1, 1);
    printf("%d\n", res);
    return 0;
}