引言

上篇我們介紹了多源BFS的相關背景知識，本篇我們將結合具體題目分析，進一步深化對于BFS算法的理解運用。

一、01矩陣

1.1 題目鏈接：https://leetcode.cn/problems/01-matrix/description/

1.2 題目分析：

• 給定一個由 0 和 1 組成的矩陣 mat ，請輸出一個大小相同的矩陣，其中每一個格子是 mat 中對應位置元素到最近的 0 的距離。

• 兩個相鄰元素間的距離為 1 。

1.3 思路講解：

返回的矩陣中，原來為0的節點，保持為0即可，而原來為1的節點，則指應修改為到最近的0的距離

• 根據上篇了解的多源bfs的基礎知識，我們在本題中有多個起點，即矩陣中原來為1的節點
• 與bfs求取最短路徑相同，我們需要將起點入隊列，但是此處可以采取正難則反的思想，把0當作起點，求取最近的1

這是由于我們把1當作起點進行遍歷時，需要統計存儲多條路徑，在進行比較時較為繁瑣

• 由于要返回同等規模的矩陣dis，我們可以在將起點入隊列時，同步將dis中相應的節點初始化為0，-1則表示尚未找到最短路徑的起點
• 之后采取上下左右層序遍歷的方式，記錄各源點所對應的最短距離

1.4 代碼實現：

class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int m=mat.size(),n=mat[0].size();//全部初始化為-1，表示尚未計算出最短路徑vector<vector<int>> dis(m,vector<int>(n,-1));queue<pair<int,int>> q;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(mat[i][j]==0){dis[i][j]=0;q.push({i,j});}}}while(q.size()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i],y=b+dy[i];if(x>=0 && x<m && y>=0 && y<n && dis[x][y]==-1){q.push({x,y});dis[x][y]=dis[a][b]+1;//步數加1}}}return dis;}
};

二、飛地的數量

2.1 題目鏈接：https://leetcode.cn/problems/number-of-enclaves/description/

2.2 題目分析：

• 給你一個大小為 m x n 的二進制矩陣 grid ，其中 0 表示一個海洋單元格、1 表示一個陸地單元格。
• 返回其中被0包圍的連續1的數量（可以理解為一些相鄰的1組成島嶼，被海洋包圍）
• 邊界上的1不能算作島嶼

2.3 思路講解：

乍一看會感覺無從下手，找不出與多源bfs算法的關系，但如果同樣采取正難則反的思想，就迎刃而解了：

• 我們把1當作起點，進行多源bfs的遍歷，如果在上下左右四個方向的遍歷過程中，找到了1，則說明這是一塊與邊界1相鄰的陸地，無法形成島嶼
• 在全部遍歷完成后，原數組內為1且對應標記數組為false的節點，則為一塊島嶼

2.4 代碼實現：

class Solution {
public:int dx[4] = { 0,0,-1,1 };int dy[4] = { 1,-1,0,0 };int numEnclaves(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<bool>> vis(m, vector<bool>(n));//標記數組queue<pair<int, int>> q;//先將邊界的1入隊列for (int i = 0; i < m; i++){if (grid[i][0] == 1){q.push({ i,0 });vis[i][0] = true;}if (grid[i][n - 1] == 1){q.push({ i,n - 1 });vis[i][n - 1] = true;}}for (int j = 0; j < n; j++){if (grid[0][j] == 1){q.push({ 0,j });vis[0][j] = true;}if (grid[m - 1][j] == 1){q.push({ m - 1,j });vis[m - 1][j] = true;}}//多源bfswhile (q.size()){auto [a, b] = q.front();q.pop();vis[a][b] = true;for (int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){q.push({ x,y });vis[x][y] = true;}}}//統計結果int ret = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 1 && vis[i][j] == false){ret++;}}}return ret;}
};

三、地圖中的最高點

3.1 題目鏈接：https://leetcode.cn/problems/map-of-highest-peak/description/

3.2 題目分析：

• 給你一個大小為 m x n 的整數矩陣 isWater ，它代表了一個由 陸地 和 水域 單元格組成的地圖。

如果 isWater[i][j] == 0 ，格子 (i, j) 是一個 陸地 格子。
如果 isWater[i][j] == 1 ，格子(i, j) 是一個 水域 格子。

• 水域的高度必須為0，相鄰的格子之間高度差最大為1
• 要求返回一共m x n的矩陣，使得矩陣中的最高高度值最大

3.3 思路講解：

本題與01矩陣類似，我們只需要把遍歷矩陣，將所有水域入隊列，之后在bfs遍歷過程中，將相鄰的陸地高度更新為dis[x][y]=dis[a][b]+1即可

3.4 代碼實現：

class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int m=isWater.size(),n=isWater[0].size();vector<vector<int>> dis(m,vector<int>(n,-1));//返回數組queue<pair<int,int>> q;//將水域入隊列for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(isWater[i][j]==1){q.push({i,j});dis[i][j]=0;//水域的高度為0}}}while(q.size()){int sz=q.size();while(sz--){auto [a,b]=q.front();q.pop();//上下左右進行遍歷for(int i=0;i<4;i++){int x=a+dx[i],y=b+dy[i];if(x>=0 && x<m && y>=0 && y<n && !isWater[x][y] && dis[x][y]==-1)//條件為不越界并且為陸地且為被遍歷過{q.push({x,y});dis[x][y]=dis[a][b]+1;}}}}return dis;}
};

四、地圖分析

4.1 題目鏈接：https://leetcode.cn/problems/as-far-from-land-as-possible/description/

4.2 題目分析：

• 有一份大小為 n x n 的 網格 grid，上面的每個 單元格 都用 0 和 1 標記好了。其中 0 代表海洋，1 代表陸地。
• 請你找出一個海洋單元格，這個海洋單元格到離它最近的陸地單元格的距離是最大的，并返回該距離。如果網格上只有陸地或者海洋，請返回 -1。
• 我們這里說的距離是「曼哈頓距離」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 這兩個單元格之間的距離是 |x0 - x1| + |y0 - y1| 。

4.3 思路講解：

• 與上題思路基本相同，采取同樣策略，將海洋入隊列層序遍歷即可
• 注意距離的計算方式

4.4 代碼實現：

class Solution {
public:int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};int m,n;int ret=-1;//最大高度int maxDistance(vector<vector<int>>& grid) {m=grid.size(),n=grid[0].size();vector<vector<int>> dis(m,vector<int>(n,-1)) ;queue<pair<int,int>> q;//將陸地入隊列for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){dis[i][j]=0;q.push({i,j});}}}while(q.size()){auto [a,b]=q.front();q.pop();for(int i=0;i<4;i++){int x=a+dx[i],y=b+dy[i];if(x>=0 & x<m && y>=0 && y<n && grid[x][y]==0 && dis[x][y]==-1){q.push({x,y});dis[x][y]=dis[a][b]+1;ret=max(ret,dis[x][y]);//更新高度}}}return ret;}
};

小結

本篇關于多源bfs的介紹就暫告段落啦，希望能對大家的學習產生幫助，歡迎各位佬前來支持斧正！！！