cam thối

from collections import deque
def oranges_rotting_opt(grid):
    q = deque()
    time, fresh = 0, 0
    ROWS, COLS = len(grid), len(grid[0])
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1: fresh += 1
            if grid[r][c] == 2: q.append((r, c))
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while q and fresh > 0:
        for i in range(len(q)):
            r, c = q.popleft()
            for dr, dc in directions:
                row, col = r + dr, c + dc
                if 0 <= row < ROWS and 0 <= col < COLS and grid[row][col] == 1:
                    grid[row][col] = 2
                    q.append((row, col))
                    fresh -= 1
        time += 1
    return time if fresh == 0 else -1

def oranges_rotting_brute(grid):
    rows, cols = len(grid), len(grid[0])
    time = 0
    while True:
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                            to_rot.append((nr, nc))
        if not to_rot: break
        for r, c in to_rot: grid[r][c] = 2
        time += 1
    for row in grid:
        if 1 in row: return -1
    return time