办文明网站做文明网民活动方案,徐州企业建站系统模板,广州网站建设网页制作开发,知名企业题目#xff1a; 腐烂的橘子
在给定的 m x n 网格 grid 中#xff0c;每个单元格可以有以下三个值之一#xff1a; 值 0 代表空单元格#xff1b; 值 1 代表新鲜橘子#xff1b; 值 2 代表腐烂的橘子。
每分钟#xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子…题目 腐烂的橘子
在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一 值 0 代表空单元格 值 1 代表新鲜橘子 值 2 代表腐烂的橘子。
每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。 解题思路
这道题可以使用广度优先搜索BFS来解决。我们首先将所有初始状态为腐烂的橙子加入队列然后进行广度优先搜索。在每一轮搜索中我们从队列中取出腐烂的橙子尝试向上下左右四个方向传播腐烂。如果某个方向上有新鲜橙子我们将其变为腐烂橙子并将其位置加入队列。重复这个过程直到队列为空即所有可能的腐烂传播都完成。
代码
public class OrangesRotting {int[][] xx {{0, -1},{-1, 0}, {0, 1}, {1, 0}};/*** 计算腐烂的橙子数量。** param grid 二维数组表示果园的状态1 代表新鲜橙子2 代表腐烂橙子0 代表空格。* return 如果所有新鲜橙子都腐烂了返回腐烂过程需要的最小天数如果无法全部腐烂则返回 -1。*/public int orangesRotting(int[][] grid) {// 获取果园的行数和列数int m grid.length, n grid[0].length, res 0;// 使用队列保存腐烂橙子的位置以便进行广度优先搜索Queueint[] queue new LinkedList();// 将所有初始状态为腐烂的橙子加入队列for(int i 0;i m;i){for(int j 0;j n;j){if(grid[i][j] 2) queue.offer(new int[]{i,j});}}// 广度优先搜索直到队列为空while(!queue.isEmpty()){// 当前队列中的橙子数量int size queue.size();// 标记当前是否有橙子腐烂boolean flag false;// 遍历当前队列中的所有橙子for(int i 0;i size;i){int[] d queue.poll();int x d[0], y d[1];// 尝试从当前腐烂橙子的位置向四个方向传播腐烂for(int[] t : xx){int xx x t[0], yy t[1] y;// 跳过越界的橙子、已经是腐烂的橙子和空格if(xx 0 || yy 0 || xx m || yy n|| grid[xx][yy] 0 || grid[xx][yy] 2) continue;// 将新鲜橙子变为腐烂橙子并将其位置加入队列标记腐烂发生grid[xx][yy] 2;flag true;queue.offer(new int[]{xx,yy});}}// 如果本次有橙子腐烂则结果加一if(flag) res;}// 检查果园中是否还有新鲜橙子有则返回 -1表示无法全部腐烂for(int i 0;i m;i){for(int j 0;j n;j){if(grid[i][j] 1) return -1;}}return res;}
}
