aboutsummaryrefslogtreecommitdiff
path: root/rotting_oranges.py
diff options
context:
space:
mode:
Diffstat (limited to 'rotting_oranges.py')
-rw-r--r--rotting_oranges.py51
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]]))