目录

• 🌟一、了解BFS
• • 1、如何理解BFS？
  • 2、什么时候使用BFS？？
• 🌟二、AcWing 844. 走迷宫
• • ✨1、题目解读+思路
  • ✨2、AC代码 【STL版】
• 🌟三、AcWing 845. 八数码
• • ✨1、题目解读
  • ✨2、AC代码
• 四、结尾：

前言
你好啊，我是一名算法小白，蓝桥杯将至，来一起学学蓝桥杯常考算法吧，这是我的题解，先上道模板题，后面实战题，我相信你认真看完，认真把题做了，一定可以学会的。
同时欢迎关注我的专栏，用心写题解，不多bb，开干🚀🚀🚀

🌟一、了解BFS

1、如何理解BFS？

• 广度优先搜索（Breadth-First-Search），我们平常都把简称为BFS。直观地讲，它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。理解起来并不难，所以我画了一张示意图，你可以看下。

2、什么时候使用BFS？？

但一些题目出现”最少“、”最短“、”至少“的时候就可以考虑使用BFS解决

🌟二、AcWing 844. 走迷宫

尽管广度优先搜索的原理挺简单，代码实现还是稍微有点复杂， 但是也很好理解，没有DFS需要递归那么难懂

✨1、题目解读+思路

具体移动过程如下图↓

怎么实现移动操作？↓

int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0} 分别对应 上右下左的坐标

✨2、AC代码 【STL版】

#include #include #include #include using namespace std;typedef pair<int, int> PII;const int N = 110;int n, m;int g[N][N];//存储地图int d[N][N];//存储每个点到起点的距离int bfs () {    queue<PII> q;//定义坐标队列    q.push({0, 0}); //起点进队    memset(d, -1, sizeof d);//初始化各个点到原点的距离为-1     d[0][0] = 0; //先初始化再赋值    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};//(x,y)         //向四个方向扩展的坐标数组 ([上右下左]操作)    while (!q.empty()) {//当队列不为空的时候 auto t = q.front();//取出对头元素 q.pop();    //队头元素出队 for (int i = 0; i < 4; i ++) { //分别对四个操作进行遍历     int x = t.first + dx[i], y = t.second + dy[i]; //移动后的坐标     //然后就是判断这个点是否 [越界 可走的位置 没有访问过 ]     if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1 ) {  d[x][y] = d[t.first][t.second] + 1;//更新距离 也就是上个点的距离+1  q.push({x, y}); //进队     } }    }    return d[n - 1][m - 1]; //返回右下角元素到源点的距离}int main () {    cin >> n >> m;    for (int i = 0; i < n; i++) { for (int j = 0; j < m; j ++) {     cin >> g[i][j]; }    }    cout << bfs() << endl;    return 0;}

🌟三、AcWing 845. 八数码

✨1、题目解读

• 这道题，难就难在该如何用坐标来表示X的位置

✨2、AC代码

先看代码，可以发现和走迷宫差不多，巧就巧在使用字符串存储
unordered_map映射其下标，实现一维坐标与二维坐标的转化，以start举例

#include #include #include #include using namespace std;int bfs(string start){string end = "12345678x"; //正确排列 queue<string> q;    unordered_map<string, int> d;//距离   q.push(start); //读入输入的排列    d[start] = 0;//距离 int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};//xy偏移量：四个方向的移动    while(q.size())    { auto t = q.front(); q.pop();  int distance = d[t];//记录移动距离 if(t == end) return distance; //终止条件  int k = t.find('x');//查询x在字符串中的下标 int x = k / 3, y = k % 3;//转换为在矩阵中的坐标 for(int i = 0; i < 4; i++) {     int a = x + dx[i], b = y + dy[i];//移动后的坐标     //判断是否越界     if(a >= 0 && a < 3 && b >= 0 && b < 3)     {  swap(t[k], t[a * 3 + b]); //交换  //t[k]:x    t[a*3+b]:操作的对象  if(!d.count(t))//如果这种情况没有遍历过 则入队  {      d[t] = distance + 1;      q.push(t);  }  swap(t[k], t[a * 3 + b]);//需要恢复现场 防止影响其他移动操作     } }    }    //无法转换到目标状态，返回-1    return -1;}int main(){    string c, start;    //输入起始状态    for(int i = 0; i < 9; i++)    { cin >> c; start += c;    }    cout << bfs(start) << endl;    return 0;}

四、结尾：

感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下🌹🌹🌹