Walls And Gates

Posted: 14 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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