LeetCode 789. 逃脱阻碍者

题目描述

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

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

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

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

数据范围

$1 \le ghosts.length \le 100$
$ghosts[i].length == 2$
$-10^4 \le x_i, y_i \le 10^4$
同一位置可能有 多个阻碍者 。
$target.length = 2$
$-10^4 \le x_{target}, y_{target} \le 10^4$

样例

输入样例1：

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

输出样例1：

true

样例1解释：

你可以直接一步到达目的地 $(0,1)$ ，在 $(1, 0)$ 或者 $(0, 3)$ 位置的阻碍者都不可能抓住你。

输入样例2：

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

输出样例2：

false

样例2解释：

你需要走到位于 $(2, 0)$ 的目的地，但是在 $(1, 0)$ 的阻碍者位于你和目的地之间。

输入样例3：

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

输出样例3：

false

样例3解释：

阻碍者可以和你同时达到目的地。

输入样例4：

ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7]

输出样例4：

false

输入样例5：

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

输出样例5：

true

思路

怪兽如果能抓到我，怪兽只要直接去终点，在终点等我就可以了。

代码

C++

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int d = abs(target[0]) + abs(target[1]);
        for ( auto &g : ghosts )
            if ( dist(g[0], target[0], g[1], target[1]) <= d )
                return false;
        return true;
    }
    
    inline int dist(int x1, int x2, int y1, int y2)
    {
        return abs(x1 - x2) + abs(y1 - y2);
    }
};

Java

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int d = Math.abs(target[0]) + Math.abs(target[1]);
        for ( int x[] : ghosts )
            if ( Math.abs(x[0] - target[0]) + Math.abs(x[1] - target[1]) <= d )
                return false;
        return true;
    }
}