在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
解法:这一题输入广度优先的经典题目,使用队列来进行判断,一开始先进行把坏橘子入队列,题目120之前的测试用例都只是一个坏橘子开头,后面120~330或多或少都是0至3个开始.在队列中进行判断,首先是上下左右进行感染橘子,将已经感染的橘子都放入队列当中,并标记为2作为已经感染. 由于当第n次感染后,队列中不只有一个坏的橘子,他们同时开始感染,时间不能累加上去,所以在队列中,我将他设为同一个的时间点.利用队列中的数量进行循环判断,是不是属于统一个时间点的,当前队列中的都是同一个时间点的,每个时间点为1,全部加起来的时间点就是答案.
while (!queue.isEmpty()){ count++; int n=queue.size(); for(int j=0;j<n;j++){ Node node=queue.remove(); .....}}题目中有一些奇怪的数组,进行判断即可,比如 [[0]],[[0,2,2],[[1]],这样的单独处理即可
boolean have1=false; //新鲜的有没有 boolean have2=false;//腐烂的有没有 ..... if(!have1||!have2){ //坏的和好的都有 if(!have1&&!have2) return 0; //橘子都没有 if(!have1) return 0;//新鲜的没有 if(!have2) return -1; }完整代码如下
public int orangesRotting(int[][] grid) { Queue<Node> queue=new LinkedList<>(); int[] dirx = {0,0,-1,1}; int[] diry = {-1,1,0,0};// 上下左右 boolean have1=false; //新鲜的有没有 boolean have2=false;//腐烂的有没有 for (int r = 0; r < grid.length; ++r) //坏的全部入队 for (int c = 0; c < grid[0].length; ++c){ if (grid[r][c] ==2) { have2=true; Node start=new Node(r,c); queue.offer(start); } if(grid[r][c] ==1) have1=true; } if(!have1||!have2){ //坏的和好的都有 if(!have1&&!have2) return 0; //橘子都没有 if(!have1) return 0;//新鲜的没有 if(!have2) return -1; } int count=-1; while (!queue.isEmpty()){ count++; int n=queue.size(); for(int j=0;j<n;j++){ Node node=queue.remove(); for (int i = 0; i <4 ; i++) { Node nextNode=new Node(node.x+dirx[i],node.y+diry[i]); if(nextNode.x>=0&&nextNode.x<grid.length&&nextNode.y>=0&&nextNode.y<grid[0].length //边界条件 &&grid[nextNode.x][nextNode.y]==1 //下一节点等于1 ){ grid[nextNode.x][nextNode.y]=2;//访问过了 queue.offer(nextNode); } } } } //检查 for (int[] row: grid) for (int v: row) if (v == 1) return -1; return count; } class Node{ int x; int y; Node(int x,int y){ this.x=x; this.y=y; } }类似的问题 130 .围绕的区域,也是走迷宫的问题,只要把边界节点放入,遍历上下左右,再直接修改就行
