题目的链接在这里:https://leetcode-cn.com/problems/rotting-oranges/
值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。
每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。
多维BFS
代码如下:
class Solution { public int orangesRotting(int[][] grid) { //0表示空格 1表示新鲜桔子 2表示腐烂的桔子 用来统计时间 要么就是先统计 这个新鲜桔子的数量 int count=0; int time=0; Queue<int[]> queue=new LinkedList<>(); for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(grid[i][j]==1){ count++; } //如果是腐烂橘子 那就需要放进去了 if(grid[i][j]==2){ queue.add(new int[]{i,j}); } } } //这里进行初始判断 如果直接count等于0了 那就是0 了 if(count==0){ return 0; } //然后就需要 进行判断 int [][] step={{0,1},{0,-1},{-1,0},{1,0}}; while (!queue.isEmpty()){ //每次都是时间加一 time++; int size=queue.size(); for(int i=0;i<size;i++){ //然后从他的四周开始扩散 int[] poll = queue.poll(); for(int j=0;j<4;j++){ int newX=poll[0]+step[j][0]; int newY=poll[1]+step[j][1]; //然后就是判断 没有越界 然后是新鲜的桔子吧 if(newX>=0&&newX<grid.length&&newY>=0&&newY<grid[0].length&&grid[newX][newY]==1){ //那就把他变成不是新鲜桔子 并且 桔子总数减1 count--; //然后进队列 grid[newX][newY]=2; queue.add(new int[]{newX,newY}); } } } } //最后判断 新鲜桔子有没有全都变成不新鲜的 return count==0?time-1:-1; } }