简单的广度优先搜索(BFS)问题:用队列存储每批腐烂的橘子。按批次取出腐烂的橘子,取出腐烂橘子的同时放入由新鲜变腐烂的橘子。
import java.util.LinkedList; import java.util.Queue; class Solution { int[][]
dist= {{-1,0},{1,0},{0,1},{0,-1}};//上下左右四个方向 public int orangesRotting(int[][]
grid) { int time = 0;//计时 Queue<int[]> queue = new LinkedList<int[]>(); int n =
grid.length; int m = grid[0].length; boolean[][] booleans = new boolean[n][m];
for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(grid[i][j] == 2){
//首批腐烂的橘子赋值为true,防止重复遍历 queue.offer(new int[]{i,j});//腐烂的橘子加入队列 booleans[i][j] =
true; } if(grid[i][j] == 0){//空单元格不做处理,防止遍历设值为true booleans[i][j] = true; } } }
int[] a = new int[2]; while(!queue.isEmpty()){ int num = queue.size();
//每批腐烂橘子的个数 int flag = 0;//若腐烂橘子能感染新鲜的橘子就改变flag的值。 for(int number = 0;number <
num;number++){ a = queue.poll(); for(int i = 0;i < 4;i++){ int x = a[0] + dist[i
][0]; int y = a[1] + dist[i][1]; if(x>=0&&y>=0&&x<n&&y<m&&booleans[x][y]!=true){
grid[x][y] = 2; queue.offer(new int[]{x,y}); booleans[x][y] = true; flag = 1; }
} } if(flag == 1){ time++; } } //遍历所有单元格,若存在新鲜橘子则返回-1,否则返回时间。 for(int i = 0; i <
n;i++){ for(int j = 0;j < m;j++){ if(grid[i][j] == 1){ return -1; } } } return
time; } }

技术
©2019-2020 Toolsou All rights reserved,
TypeScript:函数类型接口8道大厂指针笔试题让你秒杀指针!!!MySQL 日期时间加减mysql 查询条件之外的数据_mysql 查询符合条件的数据查linux的操作系统版本,如何查看Linux操作系统版本?将String类型转换成Map数据类型使用uuid做MySQL主键,被老板,爆怼一顿C语言中的字符串函数和字符函数linux服务器中毒排查--基础篇C# ASCII码字符转换