Problem of the day
-1 represents a glacier crack.
0 represents basecamp.
INF represents safe passage (INF = 2^31 -1 = 2147483647 so you may assume the distance of basecamp is less than INF).
Input:
3 3
-1 0 -1
2147483647 2147483647 2147483647
0 -1 -1
Output:
-1 0 -1
1 1 2
0 -1 -1
Explanation:
For the first INF from left to right, the closest base camp is in the bottom left with a distance of 1. For the second INF, the closest base camp is just above with a distance of 1, and for the third INF, the base camp on the top middle is closest with a distance equal to 2.
The first line of the input contains an integer, ‘T’, denoting the number of test cases.
The First line of each test case contains two integers, ‘N’ and ‘M’ denoting the number of rows and columns in the ‘GRID’.
The next ‘N’ lines of each test case contain ‘M’ integers, -1, 0, or INF(2^31 - 1).
Return the modified ‘GRID’ by updating the distance to the closest base camp.
1 <= T <= 10
1 <= N,M <= 250
Time Limit: 1 sec
2
3 3
-1 0 -1
2147483647 2147483647 2147483647
0 -1 -1
4 3
-1 0 -1
-1 2147483647 -1
-1 -1 -1
-1 2147483647 -1
-1 0 -1
1 1 2
0 -1 -1
-1 0 -1
-1 1 -1
-1 -1 -1
-1 2147483647 -1
Test 1:
For the first INF from left to right, the closest base camp is in the bottom left with a distance of 1. For the second INF, the closest base camp is just above with a distance of 1, and for the third INF, the base camp on the top middle is closest with a distance equal to 2.
Test 2:
For the first INF from above, the closest base camp in the top middle is closest with a distance equal to 1. While for the second INF it is not possible to reach any base camp.
2
3 3
-1 0 -1
2147483647 2147483647 2147483647
2147483647 2147483647 2147483647
4 3
-1 0 -1
-1 2147483647 -1
-1 0 -1
-1 2147483647 -1
-1 0 -1
2 1 2
3 2 3
-1 0 -1
-1 1 -1
-1 0 -1
-1 1 -1