图论----2.腐烂的橘子

题目链接

/**

            腐烂传染:每次腐烂的橘子会传染其四周的橘子,一共需要多少次所有橘子都腐烂。

            广搜BFS:

                    首先遍历grid,将所有\"腐烂的橘子\"添加到队列中,记录当前队列中元素个数(区分圈层)。

                    再依次取出当前队列中的元素,并将其四周的\"橘子\"入队,修改状态为腐烂。

                    重复上述过程知道队列为空,代表全部腐烂,每圈代表传染一次,自增记录即可。

                    访问过的\"橘子\"设置为2,避免重复访问。

            细节优化:

                    初始化时维护变量 freshCount判断初始有无新鲜橘子,以及处理结束后是否还有无法被感染的橘子。

                    维护布尔变量 isEventOccurred判断该轮是否有橘子被感染,有才自增结果;

                                false代表已经全部感染或有无法被感染的,此时无需增加结果

*/

class Solution { private int res; //避免重复传参 private int[][] grid; private int row; private int column; public int orangesRotting(int[][] grid) { /** 腐烂传染:每次腐烂的橘子会传染其四周的橘子,一共需要多少次所有橘子都腐烂。 广搜BFS:  首先遍历grid,将所有\"腐烂的橘子\"添加到队列中,记录当前队列中元素个数(区分圈层)。  再依次取出当前队列中的元素,并将其四周的\"橘子\"入队,修改状态为腐烂。  重复上述过程知道队列为空,代表全部腐烂,每圈代表传染一次,自增记录即可。  访问过的\"橘子\"设置为2,避免重复访问。 细节优化:  初始化时维护变量 freshCount判断初始有无新鲜橘子,以及处理结束后是否还有无法被感染的橘子。  维护布尔变量 isEventOccurred判断该轮是否有橘子被感染,有才自增结果;  false代表已经全部感染或有无法被感染的,此时无需增加结果 */ this.grid = grid; this.row = grid.length; this.column = grid[0].length; //记录新鲜橘子数 int freshCount = 0; //便于处理 方向的转换 int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //初始化 遍历,将所有\"腐烂的橘子\"入队 Queue queue = new ArrayDeque(); for(int i = 0; i < row; i++) { for(int j = 0; j < column; j++) { if(grid[i][j] == 2) {  queue.add(new int[]{i,j}); } else if(grid[i][j] == 1) {  freshCount++; } } } if(freshCount == 0) return 0; //初始无新鲜橘子 //开始处理 while(!queue.isEmpty()) { //记录当前size 区分圈层 int size = queue.size(); boolean isEventOccurred = false; //处理当前层 for(int i = 0; i = 0 && newX = 0 && newY  0) return -1; return res; }}