總結leetcode75中的圖廣度優先搜索算法題解題思路。
上一篇：力扣75——圖深度優先搜索

1 迷宮中離入口最近的出口

題目：

給你一個 m x n 的迷宮矩陣 maze （下標從 0 開始），矩陣中有空格子（用 '.' 表示）
和墻（用 '+' 表示）。同時給你迷宮的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一開始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移動一個格子。你不能進入墻所在的格子，
你也不能離開迷宮。你的目標是找到離 entrance 最近 的出口。出口 的含義是 maze 
邊界 上的 空格子。entrance 格子 不算 出口。請你返回從 entrance 到最近出口的最短路徑的 步數 ，如果不存在這樣的路徑，請你返回 -1 。

題解：
廣度優先搜索。
將與入口相鄰的空格子壓入隊列。
然后用while循環遍歷隊列中的格子，每個訪問過的格子都要做標記（記錄它到入口的距離，并將狀態設置為已訪問）。
如果當前格子為出口，則返回距離d+1。
如果訪問玩所有格子，則返回-1。

class Solution {
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int m = maze.size();int n = maze[0].size();// 上下左右四個相鄰坐標對應的行列變化量vector<int> dx = {1, 0, -1, 0};vector<int> dy = {0, 1, 0, -1};queue<tuple<int, int, int>> q;// 入口加入隊列并修改為墻q.emplace(entrance[0], entrance[1], 0);maze[entrance[0]][entrance[1]] = '+';while (!q.empty()){auto [cx, cy, d] = q.front();q.pop();// 遍歷四個方向相鄰坐標for (int k = 0; k < 4; ++k){int nx = cx + dx[k];int ny = cy + dy[k];// 新坐標合法且不為墻if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == '.'){if (nx == 0 || nx == m - 1 || ny == 0 || ny == n - 1){// 新坐標為出口，返回距離作為答案return d + 1;}// 新坐標為空格子且不為出口，修改為墻并加入隊列maze[nx][ny] = '+';q.emplace(nx, ny, d + 1);}}}// 不存在到出口的路徑，返回 -1return -1;}
};

2 腐爛的橘子

題目：

在給定的 m x n 網格 grid 中，每個單元格可以有以下三個值之一：值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。返回 直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，返回 -1 。

題解：
廣度優先搜索。
定義矩陣dis，記錄每個橘子是從第幾天開始腐爛的。-1表示未腐爛或者沒有橘子。
先找出所有腐爛的句子，并將其位置存入隊列Q。
while遍歷Q中的爛橘子，如果爛橘子grid[i][j]的周圍有未腐爛的橘子，則將對應的dis值改為dis[i][j]+1，并將該橘子的位置壓入隊列Q。
Q為空之后，查看是否全部腐爛。

class Solution {int cnt;int dis[10][10];int dir_x[4]={0, 1, 0, -1};int dir_y[4]={1, 0, -1, 0};
public:int orangesRotting(vector<vector<int>>& grid) {queue<pair<int,int> >Q;memset(dis, -1, sizeof(dis));cnt = 0;int n=(int)grid.size(), m=(int)grid[0].size(), ans = 0; for (int i = 0; i < n; ++i){for (int j = 0; j < m; ++j){if (grid[i][j] == 2){Q.push(make_pair(i, j));dis[i][j] = 0;}else if (grid[i][j] == 1) cnt += 1;}}while (!Q.empty()){pair<int,int> x = Q.front();Q.pop();for (int i = 0; i < 4; ++i){int tx = x.first + dir_x[i];int ty = x.second + dir_y[i];if (tx < 0|| tx >= n || ty < 0|| ty >= m|| dis[tx][ty]!=-1 || !grid[tx][ty]) continue;dis[tx][ty] = dis[x.first][x.second] + 1;Q.push(make_pair(tx, ty));cnt -= 1;ans = dis[tx][ty];if (!cnt) break;}}return cnt ? -1 : ans;}
};

1-2 解題總結

題目共同的特點：從起始節點出發，搜索并記錄某個或全部節點到起始節點的距離。
是否能用深度優先搜索：不能，因為有些節點可以通過多條路徑到達起始節點，如果用深度優先搜索，不能保證某條深度搜索路徑算出來的距離是該節點的最短距離。