diff options
Diffstat (limited to 'rotting_oranges.py')
-rw-r--r-- | rotting_oranges.py | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/rotting_oranges.py b/rotting_oranges.py new file mode 100644 index 0000000..7d1fc5f --- /dev/null +++ b/rotting_oranges.py @@ -0,0 +1,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]])) |