问题
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent 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.
由于腐烂的橘子每次都只能影响周围的橘子，因此采用BFS。
将所有腐烂的橘子加入队列。
如果没有新鲜的橘子，则返回0。
每次出队列，如果周围有新鲜的橘子存在，则将新鲜的橘子替换为腐烂并加入队列。
每个level结束后，time+1。
最后遍历一遍，如果还有新鲜的橘子，返回-1。
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| class Solution {
public int orangesRotting(int[][] grid) {
Queue<Integer> q = new LinkedList();
int row = grid.length;
int col = grid[0].length;
int fresh = 0;
for (int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if ( grid[i][j] == 2){
q.add(i * col + j);
}
else if (grid[i][j] == 1){
fresh++;
}
}
}
if(fresh == 0){return 0;}
int count = q.size()-1;
int temp = 0;
int time = -1;
while(!q.isEmpty()){
int i = q.peek() / col;
int j = q.poll() % col;
if(i-1>=0 && grid[i-1][j] == 1){
grid[i-1][j] = 2;
q.add((i-1)*col+j);
temp++;
}
if(j-1>=0 && grid[i][j-1] == 1){
grid[i][j-1] = 2;
q.add(i*col+(j-1));
temp++;
}
if(i+1<row && grid[i+1][j] == 1){
grid[i+1][j] = 2;
q.add((i+1)*col+j);
temp++;
}
if(j+1<col && grid[i][j+1] == 1){
grid[i][j+1] = 2;
q.add(i*col+(j+1));
temp++;
}
if(count == 0){
count = temp;
temp = 0;
time++;
}
count--;
}
for (int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if ( grid[i][j] == 1){
return -1;
}
}
}
return time;
}
}
|
