大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

单源广度优先搜索(leetcode经典例题C++实现)-创新互联

文章目录
  • 01矩阵
  • 地图分析
  • 腐烂的橘子

深度优先搜索与广度优先搜索前情回顾:
深度搜索dfs与广度搜索bfs算法总结(c++ 例题)

创新互联建站服务项目包括容城网站建设、容城网站制作、容城网页制作以及容城网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,容城网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到容城省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

本节是广度优先搜索的进阶:

01矩阵

传送门:
https://leetcode.cn/problems/01-matrix/?envType=study-plan&id=suan-fa-ru-men&plan=algorithms&plan_progress=1ophias

寻找数组中的每一个元素距离最近的零的距离。

利用广度优先搜索:

  1. 设计一个临时的数组记录状态,我们标记每一个零。
  2. 利用广度搜索把每一个零所在的坐标放入队列中,遍历队列中的每一个元素,以及其上下左右四个方向,并且依次由上一个位置的值得到当前位置的值。

我们要记录数组的每一元素距离最近的零的距离,可以发现:
0距离最近的元素就是零。
1距离最近的零可以由四周的零走一步得到,因此距离是2。

  • 我们可以利用一个标记数组将初始数组中所有的0标记为1,表示我们不需要修改它的值,0的距离就是0.
  • 标记数组默认初始化为0,因此所有非零元素在标记数组都被标记为0
  • 广度优先搜索遍历每一个位置,寻找标记数组中值为0的位置,这即是我们所需要修改的位置,我们可以通过它的上一步 +1 并且把这个值放到一个结果数组中,结果数组中的存储的元素即是最后的答案。
    在这里插入图片描述
class Solution {private:
    const int dirX[4]{0,0,-1,1};
    const int dirY[4]{-1,1,0,0};
public:
    vector>updateMatrix(vector>& mat) {int nr=mat.size(),nc=mat[0].size();
        //1. 标记数组
        vector>fg_mat(nr,vector(nc));
        //2. 结果数组
        vector>dst(nr,vector(nc));
        //3. 队列:广度优先搜索
        queue>q;
        //4. 预处理: 把所有的0标记为1,代表不需要管0元素的位置,但是我们要从这里开始进行广度优先搜索
        for (int i=0;ifor (int j=0;jif (mat[i][j]==0)
                {q.emplace(i,j);
                    fg_mat[i][j]=1;
                }
            }
        }
        //5. 开始广度搜索
        while (!q.empty())
        {pairp=q.front();
            q.pop();
            //6. 遍历某个点的四个方向
            for (int i=0;i<4;i++)
            {int mx=p.first+dirX[i];
                int my=p.second+dirY[i];
           		//7. 只需要计算非零的元素的位置
                if (mx>=0 && mx=0 && my	//8. 位置更新,由上一个的值 +1得到,走了一步
                    dst[mx][my]=dst[p.first][p.second]+1;
                    q.emplace(mx,my);
                    //9. 标记这个点已经走过了
                    fg_mat[mx][my]=1;
                }
            }
        }
        return dst;
    }
};

地图分析

传送门:
https://leetcode.cn/problems/as-far-from-land-as-possible/

地图上:0代表海洋,1代表陆地。找到海洋距离陆地大的距离。 地图中只包含0和1两种。

这道题和上一道题基本类似:

我们寻找距离陆地大的海洋的坐标位置,可以看作上一题:就是求距离0的最远的距离

上一题我们已经找到了每个点距离最近的0的距离,我们只需要找到这个值大的点,即是距离大的点,这道题的答案。
在这里插入图片描述

class Solution {private:
    const int dirX[4]{0,0,-1,1};
    const int dirY[4]{-1,1,0,0};
public:
    int maxDistance(vector>& grid) {int nr=grid.size(),nc=grid[0].size();
        //1. 标记数组
        vector>fg_map(nr,vector(nc));
        //2. 结果数组
        vector>dst(nr,vector(nc));
        //3. 队列
        queue>q;
        //4. 忽略陆地:把陆地视作上一题的0,我们不考虑他们,把他们标记为1,但是要从他们开始进行广度优先搜索
        for (int i=0;ifor (int j=0;jif (grid[i][j]==1)
                {fg_map[i][j]=1;	//注意这个位置
                    q.emplace(i,j);
                }
            }
        }
        // Step: 如果队列为空或者包含全部的数组的元素,则表示全部是海洋或者陆地,返回-1
        // (1) q.size()==0  全都是0,即全部都是海洋
        // (2) q.size()==nr*nc 全部都是1,即全部都是陆地(刚才把陆地的值入队)
        if (q.size()==0 || q.size()==nr*nc)
        {//全都是海洋:0 陆地:1(队列等于总大小) 
            return -1;
        }
        //5. 队列不为空:遍历所有海洋
        while (!q.empty())
        {pairp=q.front();
            q.pop();
            for (int i=0;i<4;i++)
            {int mx=p.first+dirX[i];
                int my=p.second+dirY[i];
                //6. 遍历每一方向,广度搜索海洋距离陆地的大距离
                if (mx>=0 && mx=0 && my	//7. 更新结果数组: 由上一步 +1得到这个点的值(即是距离)
                    dst[mx][my]=dst[p.first][p.second]+1;
                    q.emplace(mx,my);
                    //8. 标记为已经走过
                    fg_map[mx][my]=1;
                }   
            }
        }
        //9. 找到dst结果的大值,因为我们要找到海洋距离陆地的大距离
        int maxnum=0;
        for (auto& x:dst)
        {for (auto& y:x)
            {maxnum=max(y,maxnum);
            }
        }
        return maxnum;
    }
};

腐烂的橘子

传送门:
https://leetcode.cn/problems/rotting-oranges/

题目:
值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
腐烂的距离每一分钟周围的四周都会腐烂,请问当所有的橘子都腐烂,一共需要多长时间,也可能会有不会腐烂的橘子,则返回-1.

我们需要:

  1. 标记数组:记录橘子的状态: 2腐烂,1正常, 0没有橘子
  2. 时间数组:记录时间状态: 0零分钟 1一分钟 … -1表示如果此位置有橘子,则为正常橘子,或者它无橘子,为空。

  1. 首先,标记数组将所有的腐烂的橘子标记为2,时间数组记录时间,如图一,这是第零分钟。
  2. 第一分钟红色为此时扩散的腐烂的橘子,表示数组更新为2(腐烂标记),时间数组更新为 1,表示第一分钟。
  3. 第二分钟蓝色为此时扩散的腐烂的橘子,表示数组更新为2,时间数组更新为 2,表示第二分钟。
  4. 第三分钟绿色为此时扩散的腐烂的橘子,表示数组更新为2,时间数组更新为 3,表示第三分钟。
  5. 第四分钟棕色为此时扩散的腐烂的橘子,表示数组更新为2,时间数组更新为 4,表示第四分钟。
  6. 此时:根据标记数组可知,所有的橘子都被腐烂了,即数组中无 1 出现,此时时间数组对应的大值即是最后的时间在这里插入图片描述
    没有腐烂的情况:
  • 标记数组中出现1,正常的橘子,而且队列为空,无法继续。
  • 时间数组中出现 1 ,是空或者是正常的橘子,需要对应标记数组来判断是那种情况。当然也可以直接在时间数组中再给空橘子单独设置一个值。
    在这里插入图片描述
class Solution {private:
    const int dirX[4]{0,0,-1,1};
    const int dirY[4]{-1,1,0,0};
public:
    int orangesRotting(vector>& grid) {int nr=grid.size(),nc=grid[0].size();
        vector>fg(nr,vector(nc));
        vector>time(nr,vector(nc));
        queue>q;
        for (int i=0;ifor (int j=0;j//腐烂橘子
                if (grid[i][j]==2)
                {q.emplace(i,j);
                    fg[i][j]=2;     //腐烂橘子 表示为2
                    time[i][j]=0;   //时间数组 表示为0
                }
                if (grid[i][j]==1)
                {fg[i][j]=1;     //正常橘子 表示为1
                    time[i][j]=-1;  //时间数组 表示为-1
                }
            }
        }
        while (!q.empty())
        {pairp=q.front();
            q.pop();
            for (int i=0;i<4;i++)
            {int mx=p.first+dirX[i];
                int my=p.second+dirY[i];
                if (mx>=0 && mx=0 && myfg[mx][my]=2;   //橘子变腐烂
                    time[mx][my]=time[p.first][p.second]+1;  //时间增加
                    q.emplace(mx,my);  //从下一个腐烂的橘子开始
                }
            }
        }
        int max_num=0;
        for (int i=0;ifor (int j=0;jmax_num=max(max_num,time[i][j]);
                //时间是-1,并且表示为1,则这个橘子未腐烂,返回-1
                if (time[i][j]==-1 && fg[i][j]==1)
                {return -1;
                }
            }
        }
        return max_num;
    }
};

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻名称:单源广度优先搜索(leetcode经典例题C++实现)-创新互联
标题链接:http://dzwzjz.com/article/dcigdg.html
在线咨询
服务热线
服务热线:028-86922220
TOP