Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
The Summit
EASY
15 mins
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

The Summit

Contributed by
imObscure
Easy
yellow-spark
0/40
Avg time to solve 15 mins
Success Rate 79 %
Share
0 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, Constraints, Images )
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
Reset Code
Full screen
Auto
copy-code
Console