# Escape The Ghosts
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/escape-the-ghosts)
Canonical: https://scaleengineer.com/dsa/problems/escape-the-ghosts
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [Wix](https://scaleengineer.com/companies/wix)
---
## Problem
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 <= 100`
* `ghosts[i].length == 2`
* `-104 <= xi, yi <= 104`
* There can be **multiple ghosts** in the same location.
* `target.length == 2`
* `-104 <= xtarget, ytarget <= 104`

# Approaches
## Pathfinding Simulation using BFS
This approach models the problem as a shortest path problem on a grid. It uses a general pathfinding algorithm like Breadth-First Search (BFS) to calculate the minimum number of turns for the player and each ghost to reach the target. An escape is possible only if the player's time to reach the target is strictly less than every ghost's time.
**Time:** O(N * D^2) in a general case with obstacles, where N is the number of ghosts and D is the distance. For an open grid, this approach is unnecessarily complex compared to the mathematical formula. · **Space:** O(D^2) for the BFS queue and visited set, where D is the distance.
**Pros:** General approach that can be adapted for grids with obstacles.
**Cons:** Highly inefficient for this problem due to the overhead of BFS on an open grid.; More complex to implement correctly compared to the optimal solution.
### Explanation
The core idea is to simulate the movement by finding the shortest path. Since movement is restricted to four cardinal directions and each move takes one turn, BFS is a suitable algorithm to find the minimum number of turns between two points.

**Algorithm:**
1.  First, we calculate the minimum time for the player to reach the target from the starting point `[0, 0]`. This is done by performing a BFS starting from `[0, 0]` until the `target` is reached. The number of levels traversed in the BFS gives the shortest time.
2.  Then, we iterate through each ghost.
3.  For each ghost, we calculate the minimum time it needs to reach the `target` from its starting position, again using a separate BFS.
4.  We compare the player's time with the ghost's time. If any ghost's time is less than or equal to the player's time, that ghost can intercept the player at the target. In this case, escape is impossible, and we return `false`.
5.  If we check all ghosts and find that every single one of them takes more time to reach the target than the player, it means the player can safely reach the destination. We return `true`.

While this approach is conceptually correct, it is inefficient for a grid without obstacles because BFS involves managing a queue and a visited set, which adds significant overhead compared to a direct calculation.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    // On an infinite grid, BFS is equivalent to Manhattan distance.
    // A full BFS implementation would be very slow and complex.
    // This function represents the logic of finding the shortest path length.
    private int getShortestPathTurns(int[] start, int[] end) {
        return Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]);
    }

    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int[] start = {0, 0};
        int playerTime = getShortestPathTurns(start, target);

        for (int[] ghost : ghosts) {
            int ghostTime = getShortestPathTurns(ghost, target);
            if (ghostTime <= playerTime) {
                return false;
            }
        }

        return true;
    }
}
```
*Note: The provided code snippet uses the Manhattan distance formula as a stand-in for a full BFS implementation, because a true BFS on an infinite grid is impractical. The purpose is to illustrate the logic of comparing path lengths.*
### Algorithm
- Define a function `get_shortest_path(start, end)` that uses BFS to find the minimum number of turns.
- Calculate the player's time to reach the target: `player_time = get_shortest_path([0, 0], target)`.
- Iterate through each ghost in the `ghosts` array.
- For each ghost, calculate its time to reach the target: `ghost_time = get_shortest_path(ghost_position, target)`.
- If `ghost_time <= player_time`, return `false`.
- If the loop completes, return `true`.

## Manhattan Distance Comparison
This optimal approach leverages the geometry of the 2D grid. The minimum number of turns to travel between two points `(x1, y1)` and `(x2, y2)` with only cardinal movements is given by the Manhattan distance: `|x1 - x2| + |y1 - y2|`. The player can escape if and only if they can reach the target before any ghost can. The ghosts play optimally, meaning they will try to intercept the player at the earliest possible point. The most critical interception point is the target itself. If any ghost can reach the target in the same amount of time or less than the player, it can simply wait at the target and catch the player. Therefore, we only need to compare the player's travel time to the target with each ghost's travel time to the same target.
**Time:** O(N), where N is the number of ghosts. We perform a single pass through the `ghosts` array. · **Space:** O(1), as we only use a few variables to store the distances, requiring constant extra space.
**Pros:** Extremely efficient in both time and space.; Simple and elegant solution.; Easy to implement and understand.
**Cons:** The logic is specific to the problem's constraints (open grid, cardinal movement) and not a general pathfinding solution.
### Explanation
The solution hinges on a simple comparison of travel times. The time required to travel between any two points is their Manhattan distance.

**Player's Strategy:** The player's best strategy is to move directly towards the target. Any deviation would only increase their travel time.
The time for the player to reach the target `[tx, ty]` from `[0, 0]` is `|tx - 0| + |ty - 0| = |tx| + |ty|`.

**Ghost's Strategy:** A ghost's best strategy to intercept the player is to also move directly to the point of interception. If a ghost can reach the target location faster than or at the same time as the player, it can guarantee an interception by simply going to the target and waiting. The player cannot avoid this, as any other path they take will be longer.

**Algorithm:**
1.  Calculate the player's travel time to the target. This is the Manhattan distance from `[0, 0]` to `target`.
    `playerTime = |target[0]| + |target[1]|`
2.  Iterate through the list of ghosts.
3.  For each ghost at position `[gx, gy]`, calculate its travel time to the target.
    `ghostTime = |gx - target[0]| + |gy - target[1]|`
4.  Compare the times. If for any ghost, `ghostTime <= playerTime`, it means that ghost can reach the target at or before the player. The player cannot escape. Return `false`.
5.  If the loop completes without finding any such ghost, it means the player is faster than all ghosts to the target. The player can escape. Return `true`.

This method avoids any complex simulation or pathfinding and directly computes the result with simple arithmetic.

```java
class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        // Calculate the number of turns for the player to reach the target.
        // This is the Manhattan distance from (0,0) to target.
        int playerDist = Math.abs(target[0]) + Math.abs(target[1]);

        // Check each ghost.
        for (int[] ghost : ghosts) {
            // Calculate the number of turns for the ghost to reach the target.
            // This is the Manhattan distance from the ghost's position to the target.
            int ghostDist = Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1]);

            // If any ghost can reach the target at the same time or earlier,
            // it can wait at the target and catch the player. Escape is impossible.
            if (ghostDist <= playerDist) {
                return false;
            }
        }

        // If no ghost can reach the target in time, escape is possible.
        return true;
    }
}
```
### Algorithm
- Calculate the player's time to reach the target using Manhattan distance: `playerTime = |target[0]| + |target[1]|`.
- Loop through each ghost in the `ghosts` array.
- For each ghost, calculate its time to reach the target using Manhattan distance: `ghostTime = |ghost[0] - target[0]| + |ghost[1] - target[1]|`.
- If `ghostTime <= playerTime`, the player cannot escape, so return `false`.
- If the loop finishes, it means the player is faster than all ghosts, so return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean escapeGhosts(int[][] ghosts, int[] target) {
    int tx = target[0], ty = target[1];
    for (var g : ghosts) {
      int x = g[0], y = g[1];
      if (Math.abs(tx - x) + Math.abs(ty - y) <= Math.abs(tx) + Math.abs(ty)) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool escapeGhosts(vector<vector<int>> &ghosts, vector<int> &target) {
    int tx = target[0], ty = target[1];
    for (auto &g : ghosts) {
      int x = g[0], y = g[1];
      if (abs(tx - x) + abs(ty - y) <= abs(tx) + abs(ty)) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool: tx, ty = target return all(abs(tx - x) + abs(ty - y) > abs(tx) + abs(ty) for x, y in ghosts)

```