aboutsummaryrefslogtreecommitdiff
path: root/rotting_oranges.py
blob: 7d1fc5f7e738a6e9dd728efd89e36d7c5e0edd6b (plain)
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
# 994. Rotting Oranges
from collections import deque

"""
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-directionall adjacent to a rotten orange becomes rotten. return the minimum
number of minutethat must elapse until no cell has a fresh oragne. if this is
impossible, return -1
"""


class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rows = len(grid)
        if rows == 0:
            return -1
        cols, fresh_cnt, rotten = len(grid[0]), 0, deque()
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    rotten.append((r, c))
                elif grid[r][c] == 1:
                    fresh_cnt += 1
        min_pass = 0
        while rotten and fresh_cnt > 0:
            min_pass += 1
            for _ in range(len(rotten)):
                x, y = rotten.popleft()
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    xx, yy = x + dx, y + dy
                    if xx < 0 or xx == rows or yy < 0 or yy == cols:
                        continue
                    if grid[xx][yy] == 0 or grid[xx][yy] == 2:
                        continue
                    fresh_cnt -= 1
                    grid[xx][yy] = 2
                    rotten.append((xx, yy))
        return min_pass if fresh_cnt == 0 else -1


if __name__ == "__main__":
    obj = Solution()
    print(obj.orangesRotting(grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
    print(obj.orangesRotting(grid=[[2, 1, 1], [0, 1, 1], [1, 0, 1]]))
    print(obj.orangesRotting(grid=[[0, 2]]))