Final: Spreading Rot

Lab Python Advanced 30 points

A crate is a grid: 2 is a rotten orange, 1 a fresh one, 0 empty. Every minute, each rotten orange rots the fresh oranges directly up, down, left and right of it. Print how many minutes until no fresh orange is left, or -1 if some can never rot. Use BFS starting from all rotten oranges at once.

Input

Line 1: rows cols. Then rows lines of digits separated by spaces.

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

Put every rotten orange in the queue first, with time 0.

BFS: rotting a neighbour gives it time t + 1.

Count fresh oranges; if any are left at the end, print -1.

Solution explanation

Multi-source BFS spreads from all starting points at once, so the time it reaches each orange is the true minute.

Show solution

from collections import deque
r, c = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(r)]
q = deque()
fresh = 0
for i in range(r):
    for j in range(c):
        if g[i][j] == 2:
            q.append((i, j, 0))
        elif g[i][j] == 1:
            fresh += 1
minutes = 0
while q:
    i, j, t = q.popleft()
    minutes = max(minutes, t)
    for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
        if 0 <= ni < r and 0 <= nj < c and g[ni][nj] == 1:
            g[ni][nj] = 2
            fresh -= 1
            q.append((ni, nj, t + 1))
print(minutes if fresh == 0 else -1)

Output

Answer