LeetCode: 994

While the problem 542(01 Matrix) can be solved by DP, this problem can't be. The rotting can only be propagated by attached neighbor. This can solved by BFS.

Algorithm

1. mat[][] <- copy original grid and fill with MAX_INT.
2. for each position (i, j) do:
   • if grid[i][j] == Rotten, then call BFS(i, j)
   • the BFS routine is okay to stop when mat[][] value isn't worth changing. (That fresh orange has another nearer rotten orange.)
3. if there is a position (i, j) such that grid[i][j]==Fresh and mat[i][j]==MAX_INT, return -1
4. return max(mat[i][j]) such that grid[i][j] != MAX_INT

Python code

import sys
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        Empty, Fresh, Rotten = 0, 1, 2

        m, n = len(grid), len(grid[0])

        dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
        def bfs(i, j):
            queue = [(i, j, 0)]
            while queue:
                x, y, d = queue.pop(0)
                for k in range(4):
                    i, j = x+dx[k], y+dy[k]
                    if -1<i<m and -1<j<n and \
                        grid[i][j] == Fresh and \
                        time[i][j] > d+1:
                        time[i][j] = d+1
                        queue.append((i, j, d+1))

        MAX_INT = sys.maxsize
        time = [[MAX_INT for j in range(n)] for i in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == Rotten:
                    time[i][j] = 0
                    bfs(i, j)

        max_time = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == Empty:
                    continue
                if grid[i][j] == Fresh and time[i][j] == MAX_INT:
                    return -1
                max_time = max(max_time, time[i][j])

        return max_time