Problem: Given a matrix of dimension m*n. There are x number of penguins standing on some cell(i,j) in the matrix initially(none of the penguin are on the same cell). And there are some safe spots/cells in the matrix. Our job is figure out the minimum time for penguins to reach the safe spot with following conditions:
- If a spot is already taken by some penguin, any other penguin cannot take that spot.
- While traversing, If some penguin passes through cell (i,j) in its path to reach some safe spot, it is banned for other penguins to use that cell.
Print -1 in case if it not possible for all penguins to reach to some safe spot.
Penguins can move in four directions i.e either up, down, left, right. All penguins can move to one of the adjacent cells in 1 unit of time.
Let me know if the problem statement is not clear.
Test case:
P1 . . P2
. S S .
. . . .
S S . .
P1 and P2 are penguins and they are standing on cell (0,0) and (0,3) initially and there are multiple safe spot in this example located at (1,1), (1,2), (3,0) and (3,1). The minimum time for both penguin to reach at the safe spot will be 2.
Output: 2
Test case:
. S . .
P1 . P2 P3
. S S .
. . . .
Output: 2
There is a single solution possible for this test case, P1 has to follow:(1,0)->(0,0)->(0,1), P1 cannot use the path:(1,0)->(1,1)->(0,1) because if P1 uses this path then (1,1) will get banned for P2 to use and we won't be able to take P2 on safe spot.
Would love to hear about your approach.
Do all the x penguins start at cell[i][j] ? And what does the second point mean ? is it like that if a penguin goes though a certain path then any other penguin cannot travel through any of the cells in the path ?
Yes, if any penguin uses a cell, then any other penguin wont be able to use the same cell.
My guy just revived a dead blog by replying (again) to a clarification question from 2 years ago
missread the statement(part about min time)