# 789  Escape The Ghosts

## 789. [Escape The Ghosts](https://leetcode.com/problems/escape-the-ghosts/description/)

## 1. Question

You are playing a simplified Pacman game. You start at the point`(0, 0)`, and your destination is`(target[0], target[1])`. There are several ghosts on the map, the i-th ghost starts at`(ghosts[i][0], ghosts[i][1])`.

Each turn, you and all ghosts simultaneously \*may\* move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.) If you reach any square (including the target) at the same time as a ghost, it doesn't count as an escape.

Return True if and only if it is possible to escape.

```
Example 1:
Input:

ghosts = [[1, 0], [0, 3]]
target = [0, 1]

Output: true

Explanation:
You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to 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.
```

**Note:**

* All points have coordinates with absolute value  <=`10000`.
* The number of ghosts will not exceed`100`.

## 2. Implementation

思路: 对每个ghost的位置，我们都比较它离target位置的距离，如果有一个ghost的位置离target比玩家更近，则玩家无法escape ghost

```java
class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int distance = Math.abs(target[0]) + Math.abs(target[1]);
        for (int i = 0; i < ghosts.length; i++) {
            int curDistance = Math.abs(ghosts[i][0] - target[0]) + Math.abs(ghosts[i][1] - target[1]);
            if (curDistance < distance) {
                return false;
            }
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/google/789-escape-the-ghosts.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.