-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathDay-9 Rotting Oranges
48 lines (46 loc) · 2 KB
/
Day-9 Rotting Oranges
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
43
44
45
46
47
48
class Solution {
public int orangesRotting(int[][] grid) {
Queue<Pair<Integer, Integer>> queue = new ArrayDeque();
// Step 1). build the initial set of rotten oranges
int freshOranges = 0;
int ROWS = grid.length, COLS = grid[0].length;
for (int r = 0; r < ROWS; ++r)
for (int c = 0; c < COLS; ++c)
if (grid[r][c] == 2)
queue.offer(new Pair(r, c));
else if (grid[r][c] == 1)
freshOranges++;
//if no freshOranges then no need to iterate
if ( freshOranges==0) return 0;
// Step 2). start the rotting process via BFS
int minutesElapsed = -1;
int[][] directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while (!queue.isEmpty()) {
int size=queue.size();
while(size-->0){
Pair<Integer, Integer> p = queue.poll();
int row = p.getKey();
int col = p.getValue();
// this is a rotten orange
// then it would contaminate its neighbors
for (int[] d : directions) {
int neighborRow = row + d[0];
int neighborCol = col + d[1];
if (neighborRow >= 0 && neighborRow < ROWS &&
neighborCol >= 0 && neighborCol < COLS) {
if (grid[neighborRow][neighborCol] == 1) {
// this orange would be contaminated
grid[neighborRow][neighborCol] = 2;
freshOranges--;
// this orange would then contaminate other oranges
queue.offer(new Pair(neighborRow, neighborCol));
}
}
}
}
minutesElapsed++;
}
// return elapsed minutes if no fresh orange left
return freshOranges == 0 ? minutesElapsed : -1;
}
}