> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/graph-search/994.rotting-oranges.md).

# 994.Rotting-Oranges

## 994. Rotting Oranges

## 题目地址

<https://leetcode.com/problems/rotting-oranges/>

## 题目描述

```
In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
```

## 代码

### Approach #1 Breadth-First Search

```java
class Solution {
  int[] dr = new int[]{-1, 0, 1, 0};
  int[] dc = new int[]{0, -1, 0, 1};

  public int orangesRotting(int[][] grid) {
    int R = grid.length, C = grid[0].length;

    Queue<Integer> queue = new ArrayDeque();
    Map<Integer, Integer> depth = new HashMap();
    for (int r = 0; r < R; r++) {
      for (int c = 0; c < C; c++) {
        if (grid[r][c] == 2) {
          int code = r * C + c;
          queue.add(code);
          depth.put(code, 0);
        }
      }
    }

    int ans = 0;
    while (!queue.isEmpty()) {
      int code = queue.remove();
      int r = code / C, c = code % C;
      for (int k = 0; k < 4; k++) {
        int nr = r + dr[k];
        int nc = c + dc[k];
        if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
          grid[nr][nc] = 2;
          int ncode = nr * C + nc;
          queue.add(ncode);
          depth.put(ncode, depth.get(code) + 1);
          ans = depth.get(ncode);
        }
      }
    }

    for (int[] row : grid) {
      for (int v : row) {
        if (v == 1) {
          return -1;
        }
      }
    }

    return ans;
  }
}
```