---
# System prepended metadata

title: 0994. Rotting Oranges
tags: [Leetcode, BFS, Medium, Microsoft]

---

# 0994. Rotting Oranges
###### tags: `Leetcode` `Medium` `Microsoft` `BFS`
Link: https://leetcode.com/problems/rotting-oranges/
## 思路
经典的BFS问题 多个tree层序遍历
## Code
```java=
class Solution {
    public int orangesRotting(int[][] grid) {
        int time = 0;
        int freshOrange = 0;
        Queue<int[]> q = new LinkedList<>();
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j]==2){
                    q.add(new int[]{i,j});
                }
                else if(grid[i][j]==1){
                    freshOrange++;
                }
            }
        }
        if(freshOrange == 0) return 0;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        while(!q.isEmpty()){
            ++time;
            int size = q.size();
            for(int i = 0;i < size;i++){
                int[] cur = q.poll();
                for(int[] dir:dirs){
                    int newx = cur[0]+dir[0];
                    int newy = cur[1]+dir[1];
                    if(newx<0 || newx>=grid.length || newy<0 || newy>=grid[0].length || grid[newx][newy]!=1) continue;
                    grid[newx][newy] = 2;
                    q.offer(new int[]{newx, newy});
                    freshOrange--;
                }
            }
        }
        return freshOrange==0?time-1:-1;
    }
}
```