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 = [xtarget, ytarget] 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] = [xi, yi] represents the starting position of the ith 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.
Example 1:
Input: ghosts = [[1,0],[0,3]], target = [0,1] Output: true Explanation: 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 Explanation: 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 Explanation: The ghost can reach the target at the same time as you.
Constraints:
1 <= ghosts.length <= 100ghosts[i].length == 2-104 <= xi, yi <= 104target.length == 2-104 <= xtarget, ytarget <= 104This approach calculates the Manhattan distance from the starting point (0,0) to the target for you, and for each ghost from their starting position to the target. You can only escape if your distance to the target is strictly less than every ghost's distance to the target, meaning you reach the destination before any ghost can get there.
This C code defines a function to calculate the Manhattan distance and checks if you can escape by comparing your distance to the target with each ghost's distance.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).
This approach involves simulating every possible move for you and each ghost simultaneously. For each time step, move each entity towards the target or keep them in the same position if they're already there. This approach is generally inefficient but illustrates the problem space.
While this C implementation can theoretically simulate each move, it is essentially a version of the Manhattan Distance Comparison approach, as full simulation is infeasible for large inputs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Manhattan Distance Comparison | Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1). |
| Brute Force Simulation | Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1). |
21-year old dev destroys LeetCode, gets kicked out of school... • Fireship • 1,342,544 views views
Watch 9 more video solutions →Practice Escape The Ghosts with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor