一、题目
在给定的 m x n
网格 grid
中,每个单元格可以有以下三个值之一:
- 值
0
代表空单元格;- 值
1
代表新鲜橘子;- 值
2
代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1
。
二、示例
2.1> 示例 1:
【输入】grid = [[2,1,1],[1,1,0],[0,1,1]] 【输出】4
2.2> 示例 2:
【输入】grid = [[2,1,1],[0,1,1],[1,0,1]] 【输出】-1 【解释】左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。
2.3> 示例 3:
【输入】grid = [[0,2]] 【输出】0 【解释】因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。
提示:
- m == grid.length
- n == grid[i].length
1
<= m, n <=10
- grid[i][j] 仅为
0
、1
或2
三、解题思路
根据题目描述,我们要计算出单元格中没有新鲜橘子为止所必须经过的最小分钟数。由于腐烂的橘子可以将好的橘子也变腐烂,所以,我们需要采用某种方式,将这种橘子腐烂的轮次模拟计算出来。
这里,我们首先创建一个队列,即:Deque
。然后先将矩阵中腐烂的橘子保存到deque中。然后获取deque
中存储的腐烂橘子的个数num
,那么当num个橘子从deque中出栈之后,就表示该轮次执行完毕。
那么,当我们从队列deque
中弹出腐烂的橘子之后,我们会将该烂橘子的上
、下
、左
、右
的新鲜橘子都变为烂橘子,即:grid[x][y] = 2
。然后将刚刚变烂的句子放入到deque
中,准备作为后续下一轮需要操作的烂橘子。
那么,需要补充一点的就是,当我们计算矩阵中腐烂橘子的同时,也可以同时获得新鲜的橘子的个数fresh
,当面当我们发现fresh等于0的时候,则说明所有的好橘子都被腐烂了,返回操作的轮次数;而当我们操作完所有的腐烂橘子,而fresh依然不为0,则说明某些新鲜的橘子是不会被传染腐烂的,则直接返回-1
即可。
以上就是本题的解题思路。为了方便大家理解,请参照下图图解即可:
四、代码实现
class Solution {
int fresh = 0, minute = 0;
Deque<int[]> deque = new ArrayDeque();
public int orangesRotting(int[][] grid) {
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) deque.addLast(new int[]{i, j});
if (grid[i][j] == 1) fresh++;
}
}
while (fresh > 0 && !deque.isEmpty()) {
minute++;
int nums = deque.size();
for (int i = 0; i < nums; i++) {
int[] cell = deque.removeFirst();
int x = cell[0], y = cell[1];
rot(grid, x - 1, y); // 查看上方单元格
rot(grid, x + 1, y); // 查看下方单元格
rot(grid, x, y - 1); // 查看左侧单元格
rot(grid, x, y + 1); // 查看右侧单元格
}
}
return fresh > 0 ? -1 : minute;
}
public void rot(int[][] grid, int x, int y) {
if (x >= 0 && y >=0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
grid[x][y] = 2;
deque.addLast(new int[]{x, y});
fresh--;
}
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」
标签:994,deque,int,单元格,腐烂,grid,橘子,图解,LeetCode From: https://blog.51cto.com/u_15003301/6472094