-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.
For the matrix [[0,-1],[0,2147483647]] the updated matrix will be [[0,-1],[0,1]].
The distance between two cells having their coordinates (x1,y1) and (x2,y2) are abs(x2-x1) + abs(y2-y1).
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 50
1 <= N <= 10^4
1 <= M <= 10^4
1 <= N*M <= 10^4
Time Limit: 1 sec
Ninja and the experiment
The Summit
Distance to a Cycle in Undirected Graph
Search In A Sorted 2D Matrix
Spiral Matrix