from collections import deque


def min_minutes_to_rot(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Four possible directions

    # Initialize variables
    rotten_queue = deque()
    fresh_oranges = 0
    minutes = 0

    # Enqueue initially rotten oranges and count fresh oranges
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 2:
                rotten_queue.append((row, col))
            elif grid[row][col] == 1:
                fresh_oranges += 1

    while rotten_queue:
        # Determine the number of oranges in the current queue (for this minute)
        current_minute_oranges = len(rotten_queue)

        # Process all oranges in the current queue
        for _ in range(current_minute_oranges):
            current_rotten_row, current_rotten_col = rotten_queue.popleft()
            for dx, dy in directions:
                neighbor_row, neighbor_col = current_rotten_row + dx, current_rotten_col + dy
                # Check if the neighboring cell is within bounds and contains a fresh orange
                if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols and grid[neighbor_row][neighbor_col] == 1:
                    # Mark the neighboring orange as rotten
                    grid[neighbor_row][neighbor_col] = 2
                    fresh_oranges -= 1
                    # Enqueue the position for the next minute
                    rotten_queue.append((neighbor_row, neighbor_col))

        # Increment the minutes elapsed as a minute has passed
        minutes += 1

    # If there are still fresh oranges left, return -1; otherwise, return the minutes elapsed
    return -1 if fresh_oranges > 0 else max(0, minutes - 1)


# Driver code
def main():
    inputs = [
                [[2, 1, 0],
                 [1, 1, 1],
                 [1, 0, 0]],

                [[2, 0, 2, 0],
                 [2, 0, 2, 0],
                 [2, 0, 2, 0],
                 [2, 0, 2, 0]],

                [[1, 1, 1, 1, 1],
                 [1, 0, 0, 1, 0],
                 [0, 1, 2, 1, 1],
                 [0, 0, 1, 1, 0],
                 [1, 1, 1, 0, 0]],

                [[2, 1, 1, 1, 1, 1, 1],
                 [0, 0, 0, 0, 0, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1],
                 [1, 0, 0, 0, 0, 0, 0],
                 [1, 1, 1, 1, 1, 1, 1],
                 [0, 0, 0, 0, 0, 0, 1],
                 [1, 1, 1, 1, 1, 1, 1]],

                [[2, 0, 1],
                 [1, 0, 2],
                 [0, 1, 1]]
    ]

    for i in range(len(inputs)):
        print(i + 1, ".\t Original grid: ", inputs[i], sep="")
        print("\t Number of minutes to rot all oranges: ",
              min_minutes_to_rot(inputs[i]), sep="")
        print("-" * 100)


if __name__ == "__main__":
    main()