【算法面试必刷】994. 腐烂的橘子

目录题目题目链接思路复杂度代码题目题目链接994. 腐烂的橘子 - 力扣LeetCodehttps://leetcode.cn/problems/rotting-oranges/description/?envTypestudy-plan-v2envIdtop-100-liked思路核心模拟广度优先扩散逐层感染每一分钟所有已经腐烂的橘子会感染它们上下左右四个方向的新鲜橘子。使用一个临时标记数组tmp记录当前分钟将要被感染的新鲜橘子避免在同一分钟内重复感染因为多个腐烂橘子可能感染同一个新鲜橘子但只算一次。然后统一将这些标记的橘子变为腐烂并计时。重复直到没有新鲜橘子或无法继续感染即某分钟后没有新橘子被感染但仍有新鲜橘子存在。复杂度时间复杂度O(T × n × m)代码class Solution { public: // 用于标记下一分钟将要腐烂的橘子临时标记数组 bool tmp[1010][1010]; int ans 0; // 记录经过的分钟数 int dx[4] {1, 0, -1, 0}; // 四个方向的偏移量 int dy[4] {0, 1, 0, -1}; // 感染函数对于当前腐烂的橘子 (x,y)将其相邻的新鲜橘子标记到 tmp 中 void infect(int x, int y, vectorvectorint grid) { int n grid.size(), m grid[0].size(); for (int i 0; i 4; i) { int xx x dx[i]; int yy y dy[i]; // 越界检查 if (xx 0 || xx n || yy 0 || yy m) continue; // 如果该位置已经是腐烂的、或者是空格或者已经被标记为即将腐烂则跳过 // 注意tmp[xx][yy] 用于避免重复标记同一分钟内的同一个橘子 if (grid[xx][yy] 0 || grid[xx][yy] 2 || tmp[xx][yy]) continue; // 如果是新鲜橘子则标记为即将腐烂 if (grid[xx][yy] 1) { tmp[xx][yy] 1; } } } // 检查是否还有新鲜橘子 bool check(vectorvectorint grid) { int n grid.size(), m grid[0].size(); for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1) return false; } } return true; } // 将本轮标记为即将腐烂的橘子tmp中为1的正式变为腐烂2 void rot(vectorvectorint grid) { int n grid.size(), m grid[0].size(); for (int i 0; i n; i) { for (int j 0; j m; j) { if (tmp[i][j] 1) { grid[i][j] 2; } } } } int orangesRotting(vectorvectorint grid) { int n grid.size(), m grid[0].size(); // 如果一开始就没有新鲜橘子直接返回0 if (check(grid)) return 0; // 最多需要 n*m 分钟最坏情况每次只感染一个橘子 int maxTime n * m 1; while (maxTime--) { // 每轮开始前清空临时标记数组 memset(tmp, 0, sizeof(tmp)); // 遍历所有格子对每个腐烂的橘子进行感染标记 for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 2) { infect(i, j, grid); } } } // 将本轮被标记的橘子变为腐烂 rot(grid); ans; // 时间增加1分钟 // 检查是否还有新鲜橘子 if (check(grid)) { return ans; } } // 如果循环结束还有新鲜橘子即无法继续感染返回-1 return -1; } };