LeetCode 994—— 腐烂的橘子

1. 题目

2. 解题思路

• 1.记录下初始新鲜橘子的位置到 notRotting，我们按照行把二维数组拉成一维，所以，一个vector 就可以实现了；
• 2.如果没有新鲜橘子，那么第 0 分钟所有橘子已经腐烂，直接返回；
• 3.如果有新鲜橘子，那么我们遍历每一个新鲜橘子，查看它的上下左右是否有腐烂的橘子，如果有，代表这一分钟这个新鲜橘子会被腐烂，记录到 cur_Rotting，否则，这一分钟这个橘子仍然保持新鲜，记录到 cur_notRotting；
• 4.遍历完后，分钟数增加 1，然后，我们把这一分钟腐烂的橘子对应的位置置为 2;
• 5.如果这一分钟之后，没有腐烂的橘子总数没有变化，也就是没有橘子被腐蚀，那么跳出循环，因为余下的没有腐烂的橘子永远也不会腐烂了；
• 6.如果这一分钟有橘子被腐烂，那么，更新未被腐烂的橘子cur_notRotting 到 notRotting，重复步骤 3-6；
• 7.如果notRotting为空，代表所有橘子都被腐烂，返回分钟数，否则，有橘子不会被腐烂，返回-1；

3. 代码实现

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<int> notRotting;
        // 记录初始未腐烂的橘子位置
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1) {
                    notRotting.push_back(i * col + j);
                }
            }
        }
        if (notRotting.empty()) {
            return 0;
        }
        int minute = 0;
        while (!notRotting.empty()) {
        
            vector<int> cur_notRotting; // 这一分钟仍然没有腐烂的橘子
            vector<int> cur_Rotting; // 这一分钟腐烂的橘子
            for (int k = 0; k < notRotting.size(); ++k) {
                int i = notRotting[k] / col;
                int j = notRotting[k] % col;
                // 上下左右有腐烂的橘子，那么这个新鲜橘子会被腐烂
                if (i-1 >= 0 && grid[i-1][j] == 2) {
                    cur_Rotting.push_back(notRotting[k]);
                    continue;
                }
                if (i+1 < row && grid[i+1][j] == 2) {
                    cur_Rotting.push_back(notRotting[k]);
                    continue;
                }
                if (j-1 >= 0 && grid[i][j-1] == 2) {
                    cur_Rotting.push_back(notRotting[k]);
                    continue;
                }
                if (j+1 < col && grid[i][j+1] == 2) {
                    cur_Rotting.push_back(notRotting[k]);
                    continue;
                }
                // 否则，这个橘子继续保持新鲜
                cur_notRotting.push_back(notRotting[k]);
            }
            // 这一分钟腐烂的橘子更新状态
            for (int k = 0; k < cur_Rotting.size(); ++k) {
                int i = cur_Rotting[k] / col;
                int j = cur_Rotting[k] % col;
                grid[i][j] = 2;
            }
            minute += 1;
            // 这一分钟没有橘子被腐烂，跳出循环
            if (cur_notRotting.size() == notRotting.size()) {
                break;
            }
            // 更新未腐烂橘子的位置
            notRotting = cur_notRotting;
        }
        if (!notRotting.empty()) {
            return -1;
        } else {
            return minute;
        }
    }
};

时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。