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

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;
  }
}