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)$。