Escape The Ghosts

arraymath

Problem Statement

You are playing a simplified PAC-MAN game on an infinite 2-D grid. You start at the point [0, 0] , and you are given a destination point target = [x _target , y _target ] that you are trying to get to. There are several ghosts on the map with their starting positions given as a 2D array ghosts , where ghosts[i] = [x _i , y _i ] represents the starting position of the i ^th ghost. All inputs are integral coordinates .

Each turn, you and all the ghosts may independently choose to either move 1 unit in any of the four cardinal directions: north, east, south, or west, or stay still . All actions happen simultaneously .

You escape if and only if you can reach the target before any ghost reaches you. If you reach any square (including the target) at the same time as a ghost, it does not count as an escape.

Return true if it is possible to escape regardless of how the ghosts move, otherwise return false .

Examples

Example 1

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

Example 2

Input: ghosts = [[1,0]], target = [2,0]
Output: false
You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3

Input: ghosts = [[2,0]], target = [1,0]
Output: false
The ghost can reach the target at the same time as you.

Constraints

1 <= ghosts.length <= 100

ghosts[i].length == 2

-10 ^4 <= x _i , y _i <= 10 ^4

There can be multiple ghosts in the same location.

target.length == 2

-10 ^4 <= x _target , y _target <= 10 ^4

🤔

Medium

Difficulty

Topic Info

ModuleDSA

CategoryArray

Sub-topicMath