1
class Solution {
2
  class Pair {
3
    int i;
4
    int j;
5
    int t;
6

7
    public Pair(int i, int j, int t) {
8
      this.i = i;
9
      this.j = j;
10
      this.t = t;
11
    }
12
  }
13

14
  int ans = 0;
15
  final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
16

17
  public int orangesRotting(int[][] grid) {
18
    int countFresh = 0;
19
    Queue<Pair> q = new LinkedList<>();
20
    for (int i = 0; i < grid.length; i++) {
21
      for (int j = 0; j < grid[0].length; j++) {
22
        if (grid[i][j] == 2) {
23
          q.offer(new Pair(i, j, 0));
24
        } else if (grid[i][j] == 1) {
25
          countFresh++;
26
        }
27
      }
28
    }
29
    int count = 0;
30
    while (q.size() != 0) {
31
      Pair temp = q.poll();
32
      ans = Math.max(ans, temp.t);
33
      for (int[] d : dir) {
34
        int r = temp.i + d[0];
35
        int c = temp.j + d[1];
36
        int t = temp.t + 1;
37
        if (r >= 0 && c >= 0 && r < grid.length && c < grid[0].length && grid[r][c] == 1) {
38
          q.offer(new Pair(r, c, t));
39
          grid[r][c] = 2;
40
          count++;
41
        }
42
      }
43
    }
44
    if (count != countFresh) return -1;
45
    return ans;
46
  }
47
}