0789. Escape The Ghosts

题目信息

题号:

0789

难度:

Medium

主题:

坐标、曼哈顿距离、对抗可达性

原题:

LeetCode 0789

重点:

玩家从原点出发,玩家与所有幽灵每回合都可四方向移动一格或停留且动作同时发生;必须保证在任何幽灵碰到玩家之前到达目标,同回合相遇也算失败

题目重述

在无限二维整数网格中,你从 [0,0] 出发,要到达坐标 target。数组 ghosts 给出若干幽灵的初始坐标,多个幽灵可以位于同一位置。

每个回合中,你和每个幽灵都可以独立选择向上、下、左、右移动一个单位,或者停留不动;所有动作同时发生。若你与任一幽灵在任意格子相遇,包括同时到达目标格,则逃脱失败。

请判断是否存在一种行动方式,使你无论幽灵如何行动,都能在任何幽灵碰到你之前到达目标。可以保证逃脱时返回 true,否则返回 false。

1 <= ghosts.length <= 100;所有幽灵坐标和目标坐标的两个分量都在 [-10^4, 10^4] 范围内。

自建示例

玩家比所有幽灵更早到达目标:

输入:ghosts = [[4,0],[-2,3]], target = [1,2]
输出:true
解释:玩家到目标的最短距离为 3;两个幽灵到目标的最短距离分别为 5 和 4,因此它们都无法在玩家之前或同时到达目标阻挡玩家。

幽灵可以提前到目标等待:

输入:ghosts = [[2,1]], target = [3,1]
输出:false
解释:玩家到目标至少需要 4 回合,而幽灵只需 1 回合即可到达目标并等待;玩家无法安全抵达。