Compute nearest gate distance in grid

You are given an m x n grid representing a floor plan.

• 0 = a gate
• -1 = a blocked cell (wall/obstacle); cannot be entered
• INF = an empty cell (a large integer such as 2^31 - 1 )

For every empty cell, fill it with the Manhattan distance (number of up/down/left/right steps) to its nearest gate. If an empty cell cannot reach any gate, leave it as INF.

Requirements

• Update the grid in place .
• Movement is only in 4 directions.

Example

Input:

INF  -1   0  INF
INF INF INF  -1
INF  -1 INF  -1
0    -1 INF INF

Output:

3  -1  0  1
2   2  1 -1
1  -1  2 -1
0  -1  3  4

Constraints (typical)

• 1 <= m, n <= 200
• Grid values are only in { -1, 0, INF }