1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
int freshOranges = 0;
Queue<int[]> rottenQueue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
freshOranges++;
} else if (grid[i][j] == 2) {
rottenQueue.offer(new int[]{i, j});
}
}
}
if (freshOranges == 0) {
return 0;
}
int minutes = -1;
while (!rottenQueue.isEmpty()) {
for (int k = rottenQueue.size(); k > 0; k--) {
int[] cell = rottenQueue.poll();
int i = cell[0], j = cell[1];
for (int[] direction : DIRECTIONS) {
int nextI = i + direction[0], nextJ = j + direction[1];
if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && grid[nextI][nextJ] == 1) {
grid[nextI][nextJ] = 2;
freshOranges--;
rottenQueue.offer(new int[]{nextI, nextJ});
}
}
}
minutes++;
}
return freshOranges == 0 ? minutes : -1;
}
}
|