swordx's blog

By swordx, history, 6 weeks ago, In English

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:

  1. If a spot is already taken by some penguin, any other penguin cannot take that spot.
  2. 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.

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by swordx (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All the penguins starts on some random cell (i,j), none of them would be standing together on same cell. I will update the problem statement.

    It is our job to find the path for all penguins such we do that minimum overall time.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by swordx (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by swordx (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems like we need to find a matching between penguins and safe-spots. It is somewhat similar to this question. image showing how intersections are worse. As shown in the image, we can effectively eliminate crossing to get vertex-disjoint paths. We can just create a bipartite graph and add edges (whose weight is the manhattan distance) and find min cost matching I guess.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

missread the statement(part about min time)