Problem

Submissions

Hints & solutions

Discuss

Walls And Gates

Easy

0/40

Average time to solve is 15m

Contributed by

26 upvotes

Asked in companies

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).

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
2 2
2147483647 -1
-1 0
4 4
2147483647 -1 0 2147483647
2147483647 2147483647 2147483647 -1
2147483647 -1 2147483647 -1
0 -1 2147483647 2147483647

Sample Output 1:

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

Explanation For Sample Input 1:

Test case 1:

There is no path from the empty cell at [0.0] to the only gate at [1,1] .

Test case 2:

Sample Input 2:

2
2 3
-1 0 2147483647
-1 0 2147483647
3 3
0 -1 2147483647
0 -1 2147483647
0 -1 2147483647

Sample Output 2:

-1 0 1
-1 0 1
0 -1 2147483647
0 -1 2147483647
0 -1 2147483647

Hint 1

Hint 2

Perform BFS from each cell

Approaches (2)

Approach 1

Approach 2

Brute force, BFS

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.

Time Complexity

O(N^2 * M^2), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.

We using two nested loops for traversing each element in a matrix that will take O(N * M) time.

For each cell, we perform a BFS which can traverse on all the elements in the worst case so it will take O(N*M) time.

Total time complexity O((N * M)^2)

Space Complexity

O(N * M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the matrix.

In the worst case, the BFS queue may contain ‘N * M’ cells.

(100% EXP penalty)

Walls And Gates

Console