leetcode994.腐烂的橘子

思路源自

这里图中的腐烂的的橘子是同时对周围进行腐化，所以采用多源bfs就能解决 

多源bfs与单源bfs的区别就在于队列取出时一轮是取出队列当中的全部元素

class Solution {public int orangesRotting(int[][] grid) {int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//记录四个方向int result=0;//记录需要的分钟数int fresh=0;//记录新鲜橘子的数目Queue<int[]> queue = new ArrayDeque<>();//队列存储腐烂橘子int m = grid.length, n = grid[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if(grid[i][j]==1)fresh++;else if(grid[i][j]==2)queue.add(new int[]{i, j});}}while (!queue.isEmpty()) {int len = queue.size();while (len-- != 0) {int[] coordinate = queue.remove();//腐化四个方向上的新鲜橘子for (int[] dir : dirs) {int x = coordinate[0] + dir[0];int y = coordinate[1] + dir[1];if(x<0||y<0||x>=m||y>=n||grid[x][y]!=1)continue;queue.add(new int[]{x, y});grid[x][y]=2;fresh--;}}if(!queue.isEmpty())//下一轮还有result++;}if(fresh>0)return -1;elsereturn result;}
}