Medium

题目描述

你在一个无限的 2D 网格上玩简化版的吃豆人游戏。你从点 [0, 0] 开始，并给定一个目标点 target = [xtarget, ytarget]，你需要到达这个目标点。地图上有几个鬼魂，它们的起始位置由二维数组 ghosts 给出，其中 ghosts[i] = [xi, yi] 表示第 i 个鬼魂的起始位置。所有输入都是整数坐标。

每一回合，你和所有鬼魂都可以独立选择向四个基本方向（北、东、南、西）中的任意一个方向移动 1 个单位，或者留在原地不动。所有行动同时发生。

当且仅当你能在任何鬼魂抓到你之前到达目标时，你才能逃脱。如果你和鬼魂同时到达任何方格（包括目标），这不算作逃脱。

如果无论鬼魂如何移动，你都能逃脱，返回 true；否则返回 false。

示例 1：

输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以在 1 回合后到达目标 (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
解释：鬼魂可以和你同时到达目标。

提示：

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • 同一位置可能有多个鬼魂
  • target.length == 2
  • -10^4 <= xtarget, ytarget <= 10^4

解题思路

解题思路

这道题的核心思想是基于曼哈顿距离和最优策略的数学分析。

关键洞察：

  1. 我们和鬼魂都采用最优移动策略，即每步都朝着目标方向移动，这样能以最快速度到达目标
  2. 在2D网格中，从点(x1,y1)到点(x2,y2)的最短路径长度是曼哈顿距离：|x2-x1| + |y2-y1|
  3. 如果存在任何一个鬼魂到目标的距离小于等于我们到目标的距离，那么该鬼魂就能在我们到达目标之前或同时到达目标，使我们无法逃脱

算法步骤：

  1. 计算我们从起点[0,0]到目标的曼哈顿距离
  2. 遍历每个鬼魂，计算它到目标的曼哈顿距离
  3. 如果存在任何鬼魂的距离小于等于我们的距离，返回false
  4. 如果所有鬼魂的距离都大于我们的距离，返回true

数学证明： 这个贪心策略是正确的，因为鬼魂如果不直接向目标移动，只会增加它到达目标的时间，不会对我们更不利。而我们采用最短路径，如果在这种最优情况下都能逃脱，那么无论鬼魂如何移动我们都能逃脱。

时间复杂度为O(n)，空间复杂度为O(1)，其中n是鬼魂的数量。

代码实现

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int myDistance = abs(target[0]) + abs(target[1]);
        
        for (const auto& ghost : ghosts) {
            int ghostDistance = abs(target[0] - ghost[0]) + abs(target[1] - ghost[1]);
            if (ghostDistance <= myDistance) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        my_distance = abs(target[0]) + abs(target[1])
        
        for ghost in ghosts:
            ghost_distance = abs(target[0] - ghost[0]) + abs(target[1] - ghost[1])
            if ghost_distance <= my_distance:
                return False
        
        return True

public class Solution {
    public bool EscapeGhosts(int[][] ghosts, int[] target) {
        int myDistance = Math.Abs(target[0]) + Math.Abs(target[1]);
        
        foreach (var ghost in ghosts) {
            int ghostDistance = Math.Abs(target[0] - ghost[0]) + Math.Abs(target[1] - ghost[1]);
            if (ghostDistance <= myDistance) {
                return false;
            }
        }
        
        return true;
    }
}

var escapeGhosts = function(ghosts, target) {
    const myDistance = Math.abs(target[0]) + Math.abs(target[1]);
    
    for (const ghost of ghosts) {
        const ghostDistance = Math.abs(target[0] - ghost[0]) + Math.abs(target[1] - ghost[1]);
        if (ghostDistance <= myDistance) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有n个鬼魂，每次计算曼哈顿距离为O(1)
空间复杂度O(1)只使用常数额外空间存储距离变量

相关题目