逃脱阻碍者

难度: Medium

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

每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 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
解释：阻碍者可以和你同时达到目的地。

提示：

1 <= ghosts.length <= 100
ghosts[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
同一位置可能有 多个阻碍者 。
target.length == 2
-10⁴ <= x_target, y_target <= 10⁴

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        # 如果可以被中途拦截，鬼比人先到某个点，等人到了一起手拉手走向终点，
        # 不改变结局，但是鬼到终点的时间会比人少。 那不如直接算所有鬼到终点的时间 是不是比人快就好了
        tx,ty = target
        dis = abs(tx)+abs(ty)
        mnD = inf
        for x,y in ghosts:
            mnD = min(mnD,abs(x-tx)+abs(y-ty))
        return dis<mnD

Explain

这个题解的思路是：如果阻碍者可以中途拦截玩家，即阻碍者比玩家先到达某个点，然后等玩家到达后一起走向终点，虽然不会改变结局，但阻碍者到达终点的时间会比玩家少。所以与其计算阻碍者是否可以中途拦截，不如直接计算所有阻碍者到达终点的最短时间，看是否比玩家快。具体做法是先计算玩家到达终点的曼哈顿距离，然后计算每个阻碍者到终点的曼哈顿距离，取其中的最小值。如果玩家的距离小于阻碍者的最小距离，说明玩家可以成功逃脱。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        # 计算玩家到终点的曼哈顿距离
        tx, ty = target
        dis = abs(tx) + abs(ty)
        
        # 初始化阻碍者到终点的最小距离为正无穷
        mnD = inf
        
        # 遍历所有阻碍者
        for x, y in ghosts:
            # 计算当前阻碍者到终点的曼哈顿距离
            ghostDis = abs(x - tx) + abs(y - ty)
            # 更新阻碍者到终点的最小距离
            mnD = min(mnD, ghostDis)
        
        # 如果玩家距离小于阻碍者最小距离，说明可以成功逃脱
        return dis < mnD

Explore

在算法实现中，通过确保玩家到达终点的曼哈顿距离严格小于任何阻碍者到终点的曼哈顿距离来处理这种情况。如果玩家的距离小于阻碍者的最小距离，玩家将在任何阻碍者到达之前成功到达终点。如果玩家的距离等于阻碍者的距离，即使他们同时到达，也不算玩家成功逃脱。因此，算法只在玩家的距离严格小于阻碍者的最小距离时返回真（true），这自然排除了同时到达的情况。

在此特定问题中，使用曼哈顿距离是有效的，因为题目假设允许玩家和阻碍者每次移动只能沿x轴或y轴移动一步。这正是曼哈顿距离计算方式，即水平和垂直距离之和。这种计算假设没有障碍阻挡直线路径。如果游戏地图引入了如墙壁或其他障碍物，阻挡直线路径，那么曼哈顿距离就不再适用，需要考虑实际可行路径或使用其他路径算法（如A*或Dijkstra算法）。

选择取所有阻碍者中的最小距离是因为在决定是否能成功逃脱时，最关键的是最快能达到终点的阻碍者。如果任何一个阻碍者可以在玩家之前到达终点，玩家的逃脱就可能会失败。因此，算法中只考虑最快的那个阻碍者对玩家的威胁。平均距离或最大距离虽然提供了其他信息，但对于决定玩家能否逃脱没有直接影响。

算法中已经隐含处理了有多个阻碍者曼哈顿距离相同的情况。由于算法是取所有阻碍者到终点的最小曼哈顿距离，所以即使有多个阻碍者的距离相同，这不会影响算法的结果。算法只关心这个最小值，无论是由一个阻碍者还是多个阻碍者提供。因此，无需特别策略来处理多个相同距离的情况。