994. Rotting Oranges#

 1public int orangesRotting(int[][] grid) {
 2  Queue<int[]> q = new LinkedList<>();
 3  int freshOrangesCount = 0;
 4  int minutes = 0;
 5
 6  int m = grid.length;
 7  int n = grid[0].length;
 8
 9  for (int i = 0; i < m; ++i) {
10    for (int j = 0; j < n; ++j) {
11      if (grid[i][j] == 1) {
12        freshOrangesCount++;
13      } else if (grid[i][j] == 2) {
14        // add rotten orange cells to Q for BFS
15        q.add(new int[] { i, j });
16      }
17    }
18  }
19
20  int[][] directions = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
21  while (!q.isEmpty() && freshOrangesCount > 0) {
22    int qLen = q.size();
23
24    for (int i = 0; i < qLen; ++i) {
25      int[] ro = q.remove();
26      for (int[] direction : directions) {
27        int x = ro[0] + direction[0];
28        int y = ro[1] + direction[1];
29        if (x < 0 || x >= m || y < 0 || y >= n) {
30          continue;
31        }
32
33        if (grid[x][y] == 1) {
34          freshOrangesCount--;
35          grid[x][y] = 2;
36          q.add(new int[] { x, y });
37        }
38      }
39    }
40    minutes++;
41  }
42
43  if (freshOrangesCount > 0) {
44    return -1;
45  }
46
47  return minutes;
48}