Show problems as
Classic problem #789MediumArrayMath

Escape The Ghosts

Real-world version: Drone Race To The Beacon
Tracked in this browser only
Read Escape The Ghosts on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A courier drone sits on the depot at (0, 0) of an unbounded integer grid. A beacon waits at beacon = [bx, by], and each entry of patrols gives the starting cell of one patrol unit.

Time advances in turns. On every turn the drone and every patrol each either hold still or step one cell north, south, east or west, all at the same moment. The patrols are told the drone's whole route in advance and move to stop it.

The drone is intercepted if a patrol shares its cell at any moment, counting the turn on which the drone first stands on the beacon: a patrol arriving there on that same turn still counts as an interception. Once the drone has stood on the beacon without being intercepted it is safe and later turns do not matter.

Return true if the drone has a route that gets it onto the beacon without being intercepted, and false otherwise. The beacon may sit on the depot, and several patrols may share a starting cell.

Examples

Example 1

Input
patrols = [[-3, 4], [7, -2]], beacon = [-1, -1]
Output
true

The drone can step to (-1, 0) on turn 1 and onto the beacon on turn 2. Neither patrol can be standing on (-1, 0) by turn 1 or on (-1, -1) by turn 2, so nothing intercepts it.

Example 2

Input
patrols = [[6, 1]], beacon = [3, 3]
Output
false

The patrol can walk onto the beacon and hold still there before the drone is able to stand on it, so every route the drone might take ends in an interception.

Example 3

Input
patrols = [[1, 1], [9, 9]], beacon = [0, 3]
Output
false

The patrol starting at (1, 1) can be standing on the beacon on the same turn the drone first reaches it, and arriving together still counts as an interception. The patrol at (9, 9) is far away and never matters.

Constraints

  • 1 <= patrols.length <= 100
  • patrols[i].length == 2
  • -10^4 <= patrols[i][j] <= 10^4
  • beacon.length == 2
  • -10^4 <= beacon[i] <= 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_reach_beacon(patrols: list[list[int]], beacon: list[int]) -> bool:
Java
public boolean canReachBeacon(int[][] patrols, int[] beacon)

More on the same topics