Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from typing import List
- import copy
- from collections import deque
- def min_minutes_to_spoil(grid: List[List[int]]) -> int:
- """
- Calculate the minimum number of minutes until no fresh items remain.
- Return -1 if it's impossible for all items to spoil.
- 0: Empty cell
- 1: Fresh item
- 2: Spoiled item
- """
- # TODO: Implement your logic here
- rows=len(grid)
- cols=len(grid[0])
- queue=deque()
- fresh=0
- for r in range(rows):
- for c in range(cols):
- if grid[r][c]==2:
- queue.append((r,c))
- elif grid[r][c]==1:
- fresh+=1
- if fresh==0:
- return 0
- minutes=0
- directions=[(1,0),(-1,0),(0,1),(0,-1)]
- while queue:
- size=len(queue)
- changed=False
- for _ in range(size):
- r,c=queue.popleft()
- for dr, dc in directions:
- nr=r+dr
- nc=c+dc
- if 0<=nr<rows and 0<=nc<cols:
- if grid[nr][nc]==1:
- grid[nr][nc]=2
- fresh-=1
- queue.append((nr,nc))
- changed=True
- if changed:
- minutes+=1
- return minutes if fresh==0 else -1
- if __name__ == "__main__":
- test_cases = [
- # (grid, expected_output)
- ([[2, 1, 1], [1, 1, 0], [0, 1, 1]], 4),
- ([[2, 1, 1], [0, 1, 1], [1, 0, 1]], -1),
- ([[0, 2]], 0)
- ]
- print("--- Running Tests ---")
- for i, (grid, expected) in enumerate(test_cases, 1):
- grid_copy = copy.deepcopy(grid)
- result = min_minutes_to_spoil(grid_copy)
- if result == expected:
- print(f"Test {i}: PASS")
- else:
- print(f"Test {i}: FAIL (Expected {expected}, Got {result})")
Advertisement
Add Comment
Please, Sign In to add comment