【LeetCode每日一題】994. 腐爛的橘子 —— BFS算法（C/C++）

寫在前面：

大家好！我是一看就會(隻是背下來了)一寫就廢的菜雞，歡迎大家來與我一起進行刷題學習！！！下面先上雞湯（本菜雞），刷題前怎麼能沒有雞湯與美女呢，嘎嘎嘎 ^ - ^

“我見衆生皆無意，唯有見你動了情 ”

題目：

在給定的 m x n 網格 grid 中，每個單元格可以有以下三個值之一：

• 值 0 代表空單元格；
• 值 1 代表新鮮橘子；
• 值 2 代表腐爛的橘子。
• 每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。

傳回 直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，傳回 -1 。

示例 1：

輸入：grid = [[2,1,1],[1,1,0],[0,1,1]]

輸出：4

示例 2：

輸入：grid = [[2,1,1],[0,1,1],[1,0,1]]

輸出：-1

解釋：左下角的橘子（第 2 行， 第 0 列）永遠不會腐爛，因為腐爛隻會發生在 4 個正向上。

示例 3：

輸入：grid = [[0,2]]

輸出：0

解釋：因為 0 分鐘時已經沒有新鮮橘子了，是以答案就是 0 。

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 10

grid[i][j] 僅為 0、1 或 2

思路：

由題目我們可以知道每分鐘每個腐爛的橘子都會使上下左右相鄰的新鮮橘子腐爛，這其實是一個模拟廣度優先搜尋的過程。所謂廣度優先搜尋，就是從起點出發，每次都嘗試通路同一層的節點，如果同一層都通路完了，再通路下一層，最後廣度優先搜尋找到的路徑就是從起點開始的最短合法路徑。

觀察到對于所有的腐爛橘子，其實它們在廣度優先搜尋上是等價于同一層的節點的。

假設這些腐爛橘子剛開始是新鮮的，而有一個腐爛橘子會在下一秒把這些橘子都變腐爛，而這個腐爛橘子剛開始在的時間是 −1 ，那麼按照廣度優先搜尋的算法，下一分鐘也就是第 0 分鐘的時候，這個腐爛橘子會把它們都變成腐爛橘子，然後繼續向外拓展，是以其實這些腐爛橘子是同一層的節點。那麼在廣度優先搜尋的時候，我們将這些腐爛橘子都放進隊列裡進行廣度優先搜尋即可，最後每個新鮮橘子被腐爛的最短時間其實是以這個超級源點的腐爛橘子為起點的廣度優先搜尋得到的結果。

代碼：

struct xy{  //記錄結點
    int x;
    int y;
}node, top;

int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> book(m, vector<int> (n)); //标記是否被通路
    int ans = 0, cnt = 0; // cnt統計好橘子的個數 
    int tx[4] = {0, 1, 0, -1};
    int ty[4] = {-1, 0, 1, 0};
    queue<xy> q;
    
    for(int i = 0; i < m; i++){ //将所有壞橘子放入隊列
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 2){
                node.x = i;
                node.y = j;
                q.push(node);
                book[i][j] = 1;
            }else if(grid[i][j] == 1){
                cnt++;
            }
        }
    }
    
    while(!q.empty() && cnt > 0){
        int size = q.size();
        int cnt1 = 0;
        ans++;
        
        for(int i = 0; i < size; i++){ //層次周遊
            top = q.front();
            q.pop();
            
            for(int t = 0; t < 4; t++){ //通路四個方向
                int x1 = top.x + tx[t];
                int y1 = top.y + ty[t];
                
                if(x1 >= 0 && x1 < m && y1 >=0 && y1 < n && !book[x1][y1]){
                    if(grid[x1][y1] == 1){
                        grid[x1][y1] = 2; 
                        node.x = x1;
                        node.y = y1;
                        q.push(node);
                        book[x1][y1] = 1;
                        cnt1++;
                    }
                }
            }
        }
        cnt -= cnt1;
    }
    if(cnt != 0) return -1;
 else return ans;
}
           

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/rotting-oranges