bfs模板题目

旧城等待， 2024-03-26 14:59 64阅读 0赞

> [AcWing 844. 走迷宫 ][AcWing 844. _]  
> ![在这里插入图片描述][d1a9bc48db2543e89ca8f11e341b8aed.png]  
> 输出：8

#include <iostream>
    #include <algorithm> //pair<int, int>
    #include <cstring>   //memset(d, -1, sizeof d)
    using namespace std;
    
    const int N = 110;
    
    int n, m;
    int g[N][N];    //用来存迷宫具体的数值
    int d[N][N];    //用来存各点到起点的距离
    int dx[4] = {
        -1, 0, 1, 0}, dy[4] = {
        0, 1, 0, -1}; //方向偏移量
    pair<int, int> q[N*N]; //用数组来模拟队列, 数组的类型是int型二元组存坐标              
    
    int bfs()
    {
        
        int hh=0, tt=0;   //hh是队头, tt是队尾, 初始的时候都为0, hh==tt, 此时队为空
        q[0] = {
        0, 0};    //把起点(0, 0)入队, q数组是pair类型的队列
        memset(d, -1, sizeof d);//memset函数,<cstring>, memset(数组名, 把内容都置为-1, 数组大小)
                                //d数组是到起点的距离
        d[0][0] = 0;        //(0, 0)点到起点的距距离为0 
        while(hh <= tt)     //当队列不为空时
        {
        
            pair<int, int> t = q[hh++];//定义一个二元组变量t, 把队头给t, 准备启动
            for(int i=0; i<4; i++)      //依次遍历t的4个方向
            {
        
                int x = t.first + dx[i], y = t.second + dy[i];  //定义x, y 作为t的下一个坐标, 预备坐标
                if(x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==-1) // 如果x,y满足不撞边界, 
                                                                            //不撞墙, 和不走重复的路的条件
                {
        
                    d[x][y] = d[t.first][t.second] + 1;     //将上一个点距离起点的距离加一给当前点
                    q[++tt] = {
        x, y};   //把符合条件的x,y点入队, 插入到队尾
                }  //依次看t周围可经过的四个点,如果满足条件,就上下左右的顺序依次进队,一层一层的找
            }
        }
        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;
    }

> 这一道题目学到很多知识，`队列的使用`，以及`上下左右`进行`扩展的一种思路`  
> 那么下面还是需要总结一下bfs的一个模板，这样才能收获更多，学习算法最忌讳的就是图快而忘记了你最最最重要的是学会而不是有量没有内化。

//初始化队列
    //详细可以看看我后面出的队列算法框架
    初始化
    hh=0,tt=0;
    while(hh<=tt) //队列不为空
    {
        
    	//取出队头
    	int t=q[hh++];
    	for()
    	{
        
    		//扩展队列
    	}
    }

[AcWing 844. _]: https://www.acwing.com/problem/content/846/
[d1a9bc48db2543e89ca8f11e341b8aed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ba1abe084d0546c5a139feb675877b4c.png