原文链接: https://leetcode-cn.com/problems/escape-the-ghosts

英文原文

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.

Example 4:

Input: ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7]
Output: false

Example 5:

Input: ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]], target = [0,0]
Output: true

 

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

中文题目

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为 整数坐标 。

每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择 不动 。所有动作 同时 发生。

如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。

只有在你有可能成功逃脱时，输出 true ；否则，输出 false 。

 

示例 1：

输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。 

示例 2：

输入：ghosts = [[1,0]], target = [2,0]
输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。 

示例 3：

输入：ghosts = [[2,0]], target = [1,0]
输出：false
解释：阻碍者可以和你同时达到目的地。 

示例 4：

输入：ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7]
输出：false

示例 5：

输入：ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]], target = [0,0]
输出：true

 

提示：

• 1 <= ghosts.length <= 100
• ghosts[i].length == 2
• -104 <= xi, yi <= 104
• 同一位置可能有 多个阻碍者 。
• target.length == 2
• -104 <= xtarget, ytarget <= 104

通过代码

高赞题解

方法一：曼哈顿距离

为了逃脱阻碍者，玩家应按照最短路径向目的地移动。阻碍者为了抓住玩家，也会按照最短路径向目的地移动。由于每次移动为向四个方向之一移动一个单位，因此对于玩家和阻碍者而言，到达目的地的最短路径的距离为当前所在位置和目的地的曼哈顿距离。

用 $\text{dist}(A, B)$ 表示 $A$ 点和 $B$ 点的曼哈顿距离，曼哈顿距离的计算方法如下：

$$
\text{dist}(A, B) = \big| x_A - x_B \big| + \big| y_A - y_B \big|
$$

如果有一个阻碍者和目的地的曼哈顿距离小于玩家和目的地的曼哈顿距离，则该阻碍者可以在玩家之前到达目的地，然后停在目的地，玩家无法逃脱。

如果有一个阻碍者和目的地的曼哈顿距离等于玩家和目的地的曼哈顿距离，则该阻碍者可以和玩家同时到达目的地，玩家也无法逃脱。

如果所有的阻碍者和目的地的曼哈顿距离都大于玩家和目的地的曼哈顿距离，则玩家可以在阻碍者之前到达目的地。

如果玩家可以在阻碍者之前到达目的地，是否可能出现阻碍者在玩家前往目的地的中途拦截？答案是否定的，证明如下。

假设目的地是 $T$，初始时玩家位于 $S$，阻碍者位于 $G$，阻碍者在 $X$ 点拦截玩家。

由于阻碍者和目的地的曼哈顿距离大于玩家和目的地的曼哈顿距离，因此 $\text{dist}(G, T) > \text{dist}(S, T)$。

由于玩家会按照最短路径向目的地移动，因此如果阻碍者在 $X$ 点拦截玩家，则 $X$ 点一定在玩家前往目的地的最短路径上，满足 $\text{dist}(S, X) + \text{dist}(X, T) = \text{dist}(S, T)$。

由于 $X$ 点是拦截点，因此阻碍者到达 $X$ 点的时间早于或等于玩家到达 $X$ 点的时间，即 $\text{dist}(G, X) \le \text{dist}(S, X)$。

因此有：

$$
\begin{aligned}
\text{dist}(G, X) &\le \text{dist}(S, X) \
\text{dist}(G, X) + \text{dist}(X, T) &\le \text{dist}(S, X) + \text{dist}(X, T) \
\text{dist}(G, X) + \text{dist}(X, T) &\le \text{dist}(S, T)
\end{aligned}
$$

由于阻碍者到目的地的最短路径长度是 $\text{dist}(G, T)$，因此有

$$
\text{dist}(G, T) \le \text{dist}(G, X) + \text{dist}(X, T) \le \text{dist}(S, T)
$$

和条件 $\text{dist}(G, T) > \text{dist}(S, T)$ 矛盾。

因此当 $\text{dist}(G, T) > \text{dist}(S, T)$ 时，阻碍者不可能在玩家前往目的地的中途拦截，玩家可以成功逃脱。

基于上述分析，问题简化为计算玩家和目的地的曼哈顿距离以及每个阻碍者和目的地的曼哈顿距离，判断玩家是否可以在阻碍者之前到达目的地。

• 如果存在至少一个阻碍者和目的地的曼哈顿距离小于或等于玩家和目的地的曼哈顿距离，返回 $\text{false}$；

• 如果所有阻碍者和目的地的曼哈顿距离都大于玩家和目的地的曼哈顿距离，返回 $\text{true}$。

[sol1-Java]
class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int[] source = {0, 0};
        int distance = manhattanDistance(source, target);
        for (int[] ghost : ghosts) {
            int ghostDistance = manhattanDistance(ghost, target);
            if (ghostDistance <= distance) {
                return false;
            }
        }
        return true;
    }

    public int manhattanDistance(int[] point1, int[] point2) {
        return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
    }
}

[sol1-C#]
public class Solution {
    public bool EscapeGhosts(int[][] ghosts, int[] target) {
        int[] source = {0, 0};
        int distance = ManhattanDistance(source, target);
        foreach (int[] ghost in ghosts) {
            int ghostDistance = ManhattanDistance(ghost, target);
            if (ghostDistance <= distance) {
                return false;
            }
        }
        return true;
    }

    public int ManhattanDistance(int[] point1, int[] point2) {
        return Math.Abs(point1[0] - point2[0]) + Math.Abs(point1[1] - point2[1]);
    }
}

[sol1-JavaScript]
var escapeGhosts = function(ghosts, target) {
    const source = [0, 0];
    const distance = manhattanDistance(source, target);
    for (const ghost of ghosts) {
        const ghostDistance = manhattanDistance(ghost, target);
        if (ghostDistance <= distance) {
            return false;
        }
    }
    return true;
}

const manhattanDistance = (point1, point2) => {
    return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
}

[sol1-Python3]
class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        source = [0, 0]
        distance = manhattanDistance(source, target)
        return all(manhattanDistance(ghost, target) > distance for ghost in ghosts)

def manhattanDistance(point1: List[int], point2: List[int]) -> int:
    return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])

[sol1-Golang]
func escapeGhosts(ghosts [][]int, target []int) bool {
    source := []int{0, 0}
    distance := manhattanDistance(source, target)
    for _, ghost := range ghosts {
        if manhattanDistance(ghost, target) <= distance {
            return false
        }
    }
    return true
}

func manhattanDistance(point1, point2 []int) int {
    return abs(point1[0]-point2[0]) + abs(point1[1]-point2[1])
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

[sol1-C++]
class Solution {
public:
    int manhattanDistance(vector<int>& point1, vector<int>& point2) {
        return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]);
    }

    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        vector<int> source(2);
        int distance = manhattanDistance(source, target);
        for (auto& ghost : ghosts) {
            int ghostDistance = manhattanDistance(ghost, target);
            if (ghostDistance <= distance) {
                return false;
            }
        }
        return true;
    }
};

[sol1-C]
int manhattanDistance(int* point1, int* point2) {
    return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]);
}

bool escapeGhosts(int** ghosts, int ghostsSize, int* ghostsColSize, int* target, int targetSize) {
    int source[2] = {0, 0};
    int distance = manhattanDistance(source, target);
    for (int i = 0; i < ghostsSize; i++) {
        int ghostDistance = manhattanDistance(ghosts[i], target);
        if (ghostDistance <= distance) {
            return false;
        }
    }
    return true;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{ghosts}$ 的长度。需要计算玩家和目的地的距离，以及遍历数组 $\textit{ghosts}$ 计算每个阻碍者和目的地的距离。

• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
21105	30493	69.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言