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

文章目錄

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

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

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

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

01矩陣

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

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

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

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

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

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

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. 標記數(shù)組
        vector>fg_mat(nr,vector(nc));
        //2. 結(jié)果數(shù)組
        vector>dst(nr,vector(nc));
        //3. 隊列：廣度優(yōu)先搜索
        queue>q;
        //4. 預處理： 把所有的0標記為1，代表不需要管0元素的位置，但是我們要從這里開始進行廣度優(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. 開始廣度搜索
        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. 標記這個點已經(jīng)走過了
                    fg_mat[mx][my]=1;
                }
            }
        }
        return dst;
    }
};

地圖分析

傳送門：
https://leetcode.cn/problems/as-far-from-land-as-possible/

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

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

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

上一題我們已經(jīng)找到了每個點距離最近的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. 標記數(shù)組
        vector>fg_map(nr,vector(nc));
        //2. 結(jié)果數(shù)組
        vector>dst(nr,vector(nc));
        //3. 隊列
        queue>q;
        //4. 忽略陸地：把陸地視作上一題的0，我們不考慮他們，把他們標記為1，但是要從他們開始進行廣度優(yōu)先搜索
        for (int i=0;ifor (int j=0;jif (grid[i][j]==1)
                {fg_map[i][j]=1;	//注意這個位置
                    q.emplace(i,j);
                }
            }
        }
        // Step： 如果隊列為空或者包含全部的數(shù)組的元素，則表示全部是海洋或者陸地，返回-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. 更新結(jié)果數(shù)組： 由上一步 +1得到這個點的值（即是距離）
                    dst[mx][my]=dst[p.first][p.second]+1;
                    q.emplace(mx,my);
                    //8. 標記為已經(jīng)走過
                    fg_map[mx][my]=1;
                }   
            }
        }
        //9. 找到dst結(jié)果的大值，因為我們要找到海洋距離陸地的大距離
        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.

我們需要：

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

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

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

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ù)組 表示為0
                }
                if (grid[i][j]==1)
                {fg[i][j]=1;     //正常橘子 表示為1
                    time[i][j]=-1;  //時間數(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;  //時間增加
                    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;
    }
};

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

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

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

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

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

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

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