#994. 腐烂的橘子
题目难度：简单
题目描述
解题思路
1、BFS
做完上一道题机器人可以走的格子再来做这个思路就很清晰。
和普通bfs不同的就是，这个增加了时间（即轮次）的概念，因为每一分钟所有腐烂的橘子会同时腐蚀周围的新鲜橘子，所以在遍历时得一次性遍历完同一深度的格子。
具体做法就是先把所有的腐烂橘子入队，轮次可以理解为0，然后一次性把这些句子周围的橘子都遍历完，新被腐蚀的入队，轮次为1；再继续操作，直到队列为空或者没有新鲜橘子了。
public int orangesRotting(int[][] grid) {int round = 0,num = 0; //round表示腐烂的轮数，num保存新鲜橘子的数量int m = grid.length,n = grid[0].length; Queue<Integer> queue = new LinkedList<Integer>();int move[][] = new int[][] {{-1,0},{1,0},{0,-1},{0,1}};//上下左右四个正方向for (int i = 0; i < m; i++) { //找到所有的腐烂橘子并入队for (int j = 0; j < n; j++) {if(2 == grid[i][j]) {queue.offer(i*n + j);//将坐标转换为唯一的索引 }else if(1 == grid[i][j])num++;}}while(num > 0 && !queue.isEmpty()) {round++;int s = queue.size();//队列里面每次保存同一层的所有腐烂橘子，同一层要一起出队腐烂周围的橘子for (int i = 0; i < s; i++) {int code = queue.poll();int x = code/n,y = code%n;for (int j = 0; j < 4; j++) {int new_x = x + move[j][0];int new_y = y + move[j][1];int ncode = new_x*n+new_y;if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && 1 == grid[new_x][new_y] ) { //如果符合边界条件并且是新鲜橘子，那么腐烂grid[new_x][new_y] = 2;queue.offer(ncode);num--;}} }} if(num != 0)return -1; elsereturn round; }
1234567891011121314151617181920212223242526272829303132333435363738提交结果：
