目录

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

前言
欢迎关注我的专栏,准备写完算法基础所有题解🚀🚀🚀 专栏链接

---

🌟一、了解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 <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
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 <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

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;
}

四、结尾：

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