# 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
```python
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
```
