The Summit

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes

Problem statement

Sam is on his Himalayan trip. The trekking area can be represented as an ‘M’ x ‘N’ matrix ‘GRID’ containing safe passages, basecamps, and glacier cracks.

He can travel through safe passages and reach the nearest base camp.

GRID is initialised by 3 possible values,

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

For each cell that represents the safe passage, fill the cell with the distance to its nearest base camp. If it is impossible to reach any base camp, it should be filled with INF.

Note: Sam can not travel through cracks.

Example: 
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.
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 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).
Output format : 
Return the modified ‘GRID’ by updating the distance to the closest base camp.
Constraints : 
1 <= T <= 10
1 <= N,M <= 250
Time Limit: 1 sec
Sample Input 1 :
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
Sample Output 1 :
-1 0 -1
1 1 2
0 -1 -1
-1 0 -1
-1 1 -1
-1 -1 -1
-1 2147483647 -1
Explanation Of Sample Input 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.
Sample Input 2 :
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
Sample Output 2 :
-1 0 -1
2 1 2
3 2 3
-1 0 -1
-1 1 -1
-1 0 -1
-1 1 -1
Hint

Run BFS through all the base camps through safe passages to assign the nearest distance.

Approaches (1)
BFS

The solution to the problem lies in assigning all the connected components of cells with 0s(base camp) through the cells with INF(safe passages) in the GRID.

This can be implemented by performing a Breadth-First Search for every ‘0’ in the GRID and modifying the distance of cells with safe passages that are connected to it. To implement BFS we can first insert all the cells with 0s initially in a queue and then check for their neighbors in all 4 directions.

 

The steps are as follows :

Void BFS ([int][] GRID , [queue(int,int,int)] ‘que’)

  1. While que is not empty
    • Assign (rowNo, colNo, dis) with front tuple of que.
    • Pop the front tuple.
    • For loop for adjacent cells in all 4 directions
      • If the cell contains INF(2^31-1)
        • Update the cell in GRID with dis+1.
        • Push current (row,col,dis+1) in the que.

Void capture([char][] GRID)

  1. Create a queue ‘que’ which takes tuple for row,cloumn, and distance.
  2. For ‘row’ in range 0 to N-1.
    • For ‘col’ in range 0 to M-1.
      • If GRID[row][col] is ‘O’
        • Push (row, col,0) in que.
  3. Call BFS(GRID,que) to modify the GRID.
Time Complexity

O( N x M ), Where N and M are the numbers of rows and columns. 

 The BFS is performed for every cell that represents a base camp, which would go to NxM cells in the worst case.

Hence the time complexity is O( N x M ).

Space Complexity

O( 1 ) 

 Since we are only updating the original GRID without using any extra space.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
The Summit
Full screen
Console