Escape The Ghosts


  • 0

    Click here to see the full article post


  • 0
    L

    what if the case is : | me | | |
    | |target | ghost |

    this is a 2*3 board ,and ghost is nearer to the target , but it looks like ghost can't catch me


  • 0
    K

    @luchy0120 and you can't escape either. so escapeGhosts() returns false


  • 0

    @luchy0120 The ghost is allowed to stay put, so after reaching the target, you can never escape.


  • 0
    K

    @awice, I think the ghost doesn't have to stay put, as per "If you reach any square (including the target) at the same time as a ghost, it doesn't count as an escape", so ghost just need to move around the target


  • 0
    L

    @awice, @kimjianzsu ,First step, the ghost reach the target, I reach one step away from the target. Second step,the ghost will leave the target, and I go into the target and escape success. It's hard to give definition of "catch".


  • 0

    @luchy0120 The description was written very carefully to prevent this case. You escape if and only if when making a path that eventually reaches the escape, for any path the ghosts may take, they never touch you (even at the end.) The ghost does not have to move once reaching the target (it says "may" move), and if you do not reach the target you do not escape.


  • 0
    L

    @awice , the only way you escape is to reach the target, so the ghosts stand on the target waiting for you to come.


  • 0
    W

    You should just calculate taxi(source, target) once, instead of once for every ghost.


  • 0
    S

    So in summary, if G cannot reach S, due to problem statement, we have d(S, T) < d(G, T) . Conversely, assume that d(S,T) < d(G, T). Then there exists a point X, such that d(S, X) < d(G, X), otherwise, d(S, T) >= d(G, T). Then from triangle inequality, by going through point X, S gets to T earlier than G , and G cannot reach S. Hence, G cannot reach S iff d(S, T) < d(G, T).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.