-
Notifications
You must be signed in to change notification settings - Fork 0
/
994-rotting-oranges.py
65 lines (55 loc) · 1.87 KB
/
994-rotting-oranges.py
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
"""
In a given grid, each cell can have one of three values:
1. the value 0 representing an empty cell;
2. the value 1 representing a fresh orange;
3. the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.
Note:
1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 0, 1, or 2.
Example:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
"""
import collections
class Solution(object):
def orangesRotting(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
w = len(grid[0])
h = len(grid)
time = 0
queue = collections.deque([])
for x in range(w):
for y in range(h):
if grid[y][x] == 2:
queue.append([x, y, 0])
while queue:
x, y, time = queue.popleft()
if x - 1 >= 0 and grid[y][x - 1] == 1:
queue.append([x - 1, y, time + 1])
grid[y][x - 1] = 2
if x + 1 < w and grid[y][x + 1] == 1:
queue.append([x + 1, y, time + 1])
grid[y][x + 1] = 2
if y - 1 >= 0 and grid[y - 1][x] == 1:
queue.append([x, y - 1, time + 1])
grid[y - 1][x] = 2
if y + 1 < h and grid[y + 1][x] == 1:
queue.append([x, y + 1, time + 1])
grid[y + 1][x] = 2
for x in range(w):
for y in range(h):
if grid[y][x] == 1:
return -1
return time
if __name__ == "__main__":
grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
print(Solution().orangesRotting(grid))