單源廣度優(yōu)先搜索（leetcode經(jīng)典例題C++實(shí)現(xiàn)）-創(chuàng)新互聯(lián)

文章目錄

01矩陣
地圖分析
腐爛的橘子

深度優(yōu)先搜索與廣度優(yōu)先搜索前情回顧：
深度搜索dfs與廣度搜索bfs算法總結(jié)（c++ 例題）

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括容城網(wǎng)站建設(shè)、容城網(wǎng)站制作、容城網(wǎng)頁(yè)制作以及容城網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，容城網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到容城省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

本節(jié)是廣度優(yōu)先搜索的進(jìn)階：

01矩陣

傳送門(mén)：
https://leetcode.cn/problems/01-matrix/?envType=study-plan&id=suan-fa-ru-men&plan=algorithms&plan_progress=1ophias

尋找數(shù)組中的每一個(gè)元素距離最近的零的距離。

利用廣度優(yōu)先搜索：

設(shè)計(jì)一個(gè)臨時(shí)的數(shù)組記錄狀態(tài)，我們標(biāo)記每一個(gè)零。
利用廣度搜索把每一個(gè)零所在的坐標(biāo)放入隊(duì)列中，遍歷隊(duì)列中的每一個(gè)元素，以及其上下左右四個(gè)方向，并且依次由上一個(gè)位置的值得到當(dāng)前位置的值。

我們要記錄數(shù)組的每一元素距離最近的零的距離，可以發(fā)現(xiàn)：
0距離最近的元素就是零。
1距離最近的零可以由四周的零走一步得到，因此距離是2。

我們可以利用一個(gè)標(biāo)記數(shù)組將初始數(shù)組中所有的0標(biāo)記為1，表示我們不需要修改它的值，0的距離就是0.
標(biāo)記數(shù)組默認(rèn)初始化為0，因此所有非零元素在標(biāo)記數(shù)組都被標(biāo)記為0。
廣度優(yōu)先搜索遍歷每一個(gè)位置，尋找標(biāo)記數(shù)組中值為0的位置，這即是我們所需要修改的位置，我們可以通過(guò)它的上一步 +1 并且把這個(gè)值放到一個(gè)結(jié)果數(shù)組中，結(jié)果數(shù)組中的存儲(chǔ)的元素即是最后的答案。

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. 標(biāo)記數(shù)組
        vector>fg_mat(nr,vector(nc));
        //2. 結(jié)果數(shù)組
        vector>dst(nr,vector(nc));
        //3. 隊(duì)列：廣度優(yōu)先搜索
        queue>q;
        //4. 預(yù)處理： 把所有的0標(biāo)記為1，代表不需要管0元素的位置，但是我們要從這里開(kāi)始進(jìn)行廣度優(yōu)先搜索
        for (int i=0;ifor (int j=0;jif (mat[i][j]==0)
                {q.emplace(i,j);
                    fg_mat[i][j]=1;
                }
            }
        }
        //5. 開(kāi)始廣度搜索
        while (!q.empty())
        {pairp=q.front();
            q.pop();
            //6. 遍歷某個(gè)點(diǎn)的四個(gè)方向
            for (int i=0;i<4;i++)
            {int mx=p.first+dirX[i];
                int my=p.second+dirY[i];
           		//7. 只需要計(jì)算非零的元素的位置
                if (mx>=0 && mx=0 && my	//8. 位置更新，由上一個(gè)的值 +1得到，走了一步
                    dst[mx][my]=dst[p.first][p.second]+1;
                    q.emplace(mx,my);
                    //9. 標(biāo)記這個(gè)點(diǎn)已經(jīng)走過(guò)了
                    fg_mat[mx][my]=1;
                }
            }
        }
        return dst;
    }
};

地圖分析

傳送門(mén)：
https://leetcode.cn/problems/as-far-from-land-as-possible/

地圖上：0代表海洋，1代表陸地。找到海洋距離陸地大的距離。地圖中只包含0和1兩種。

這道題和上一道題基本類似：

我們尋找距離陸地大的海洋的坐標(biāo)位置，可以看作上一題：就是求距離0的最遠(yuǎn)的距離。

上一題我們已經(jīng)找到了每個(gè)點(diǎn)距離最近的0的距離，我們只需要找到這個(gè)值大的點(diǎn)，即是距離大的點(diǎn)，這道題的答案。
在這里插入圖片描述

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. 標(biāo)記數(shù)組
        vector>fg_map(nr,vector(nc));
        //2. 結(jié)果數(shù)組
        vector>dst(nr,vector(nc));
        //3. 隊(duì)列
        queue>q;
        //4. 忽略陸地：把陸地視作上一題的0，我們不考慮他們，把他們標(biāo)記為1，但是要從他們開(kāi)始進(jìn)行廣度優(yōu)先搜索
        for (int i=0;ifor (int j=0;jif (grid[i][j]==1)
                {fg_map[i][j]=1;	//注意這個(gè)位置
                    q.emplace(i,j);
                }
            }
        }
        // Step： 如果隊(duì)列為空或者包含全部的數(shù)組的元素，則表示全部是海洋或者陸地，返回-1
        // (1) q.size()==0  全都是0，即全部都是海洋
        // (2) q.size()==nr*nc 全部都是1，即全部都是陸地（剛才把陸地的值入隊(duì)）
        if (q.size()==0 || q.size()==nr*nc)
        {//全都是海洋：0 陸地：1（隊(duì)列等于總大?。?
            return -1;
        }
        //5. 隊(duì)列不為空：遍歷所有海洋
        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. 更新結(jié)果數(shù)組： 由上一步 +1得到這個(gè)點(diǎn)的值（即是距離）
                    dst[mx][my]=dst[p.first][p.second]+1;
                    q.emplace(mx,my);
                    //8. 標(biāo)記為已經(jīng)走過(guò)
                    fg_map[mx][my]=1;
                }   
            }
        }
        //9. 找到dst結(jié)果的大值，因?yàn)槲覀円业胶Ｑ缶嚯x陸地的大距離
        int maxnum=0;
        for (auto& x:dst)
        {for (auto& y:x)
            {maxnum=max(y,maxnum);
            }
        }
        return maxnum;
    }
};

腐爛的橘子

傳送門(mén)：
https://leetcode.cn/problems/rotting-oranges/

題目：
值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
腐爛的距離每一分鐘周圍的四周都會(huì)腐爛，請(qǐng)問(wèn)當(dāng)所有的橘子都腐爛，一共需要多長(zhǎng)時(shí)間，也可能會(huì)有不會(huì)腐爛的橘子，則返回-1.

我們需要：

標(biāo)記數(shù)組：記錄橘子的狀態(tài)： 2腐爛，1正常， 0沒(méi)有橘子
時(shí)間數(shù)組：記錄時(shí)間狀態(tài)： 0零分鐘 1一分鐘 … -1表示如果此位置有橘子，則為正常橘子，或者它無(wú)橘子，為空。

首先，標(biāo)記數(shù)組將所有的腐爛的橘子標(biāo)記為2，時(shí)間數(shù)組記錄時(shí)間，如圖一，這是第零分鐘。
第一分鐘：紅色為此時(shí)擴(kuò)散的腐爛的橘子，表示數(shù)組更新為2（腐爛標(biāo)記），時(shí)間數(shù)組更新為 1，表示第一分鐘。
第二分鐘：藍(lán)色為此時(shí)擴(kuò)散的腐爛的橘子，表示數(shù)組更新為2，時(shí)間數(shù)組更新為 2，表示第二分鐘。
第三分鐘：綠色為此時(shí)擴(kuò)散的腐爛的橘子，表示數(shù)組更新為2，時(shí)間數(shù)組更新為 3，表示第三分鐘。
第四分鐘：棕色為此時(shí)擴(kuò)散的腐爛的橘子，表示數(shù)組更新為2，時(shí)間數(shù)組更新為 4，表示第四分鐘。
此時(shí)：根據(jù)標(biāo)記數(shù)組可知，所有的橘子都被腐爛了，即數(shù)組中無(wú) 1 出現(xiàn)，此時(shí)時(shí)間數(shù)組對(duì)應(yīng)的大值即是最后的時(shí)間。
沒(méi)有腐爛的情況：

標(biāo)記數(shù)組中出現(xiàn)1，正常的橘子，而且隊(duì)列為空，無(wú)法繼續(xù)。
時(shí)間數(shù)組中出現(xiàn) 1 ，是空或者是正常的橘子，需要對(duì)應(yīng)標(biāo)記數(shù)組來(lái)判斷是那種情況。當(dāng)然也可以直接在時(shí)間數(shù)組中再給空橘子單獨(dú)設(shè)置一個(gè)值。

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;   //時(shí)間數(shù)組 表示為0
                }
                if (grid[i][j]==1)
                {fg[i][j]=1;     //正常橘子 表示為1
                    time[i][j]=-1;  //時(shí)間數(shù)組 表示為-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;  //時(shí)間增加
                    q.emplace(mx,my);  //從下一個(gè)腐爛的橘子開(kāi)始
                }
            }
        }
        int max_num=0;
        for (int i=0;ifor (int j=0;jmax_num=max(max_num,time[i][j]);
                //時(shí)間是-1，并且表示為1，則這個(gè)橘子未腐爛，返回-1
                if (time[i][j]==-1 && fg[i][j]==1)
                {return -1;
                }
            }
        }
        return max_num;
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：單源廣度優(yōu)先搜索（leetcode經(jīng)典例題C++實(shí)現(xiàn)）-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)網(wǎng)址：http://jinyejixie.com/article16/dcigdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、靜態(tài)網(wǎng)站、網(wǎng)站維護(hù)、品牌網(wǎng)站建設(shè)、小程序開(kāi)發(fā)、品牌網(wǎng)站設(shè)計(jì)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

單源廣度優(yōu)先搜索（leetcode經(jīng)典例題C++實(shí)現(xiàn)）-創(chuàng)新互聯(lián)