Walls And Gates

PROBLEM STATEMENT

You are given a matrix having ‘N’ rows and ‘M’ columns. Each cell of the matrix can only contain three values as given below:

-1 -> It denotes a wall or an obstacle

0  -> It denotes a gate

2^31 - 1 =  2147483647 ( INF ) -> An infinitely large value  denotes the empty room.

For each empty room (denoted by INF), you have to refill it with the distance to its nearest gate. If none of the gates is reachable from an empty room then the value ‘INF’ will remain as it is.

Example

For the matrix [[0,-1],[0,2147483647]] the updated matrix will be [[0,-1],[0,1]].

Note

The distance between two cells having their coordinates (x1,y1) and (x2,y2) are abs(x2-x1) + abs(y2-y1).

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The next 2*T lines describe the ‘T’ test cases.

The first line of each test case contains two space-separated positive integers ‘N’ and ‘M’ denoting the number of the rows and columns in a matrix respectively. 

The next ‘N’ lines of each test case contain ‘M’ space-separated integers among -1, 0, and 2^31 - 1.

Output Format:

The output of each test case should contain a matrix of size N x M where each empty cell will contain the distance to its nearest gate.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4  
1 <= M <= 10^4
1 <= N*M <= 10^4 

Time Limit: 1 sec

Approach 1

We will run two nested loops to traverse each empty cell of the matrix.
For each empty cell, we perform BFS from this cell to its nearest gate. We traverse on each neighbour of the cell in BFS.
While traversing we use a 2D array called distance to keep track of the distance of each empty cell to the nearest gate. Initially, all the entries in the distance are 0 to denote that this cell is not visited yet. So distance array can be used in place of visited array too.
If some cell is not visited and it is not a gate then we insert it in our queue and update our distance of this neighbouring cell to the distance current cell + 1.
If at some point in time we reached a gate then we return our final distance as the answer of the current cell.

Try Problem

Approach 2

In this approach, we calculate the minimum distance of some gate to each empty cell using multi-source BFS.
In multi-source BFS we insert all the gates in the queue initially. Then we perform our normal BFS by adding all empty neighboring cells which are not visited yet.
Once a cell enters the queue we update the value of the neighboring cell to the value of this current cell + 1.Since BFS guarantees that we search all cells of distance, d before searching cells of distance, d + 1, the distance to an empty cell must be the shortest.
After the BFS ends our matrix will be updated with the distance of the nearest gate from each empty cell.

Try Problem