789. 逃脱阻碍者

关键：算曼哈顿距离来判断

解析：简化一下 让所有的鬼都去终点等着人，如果鬼先到终点就不行，人先到终点就可。

可以证明出：如果一个阻碍者能够抓到玩家，必然不会比玩家更晚到达终点。

为了方便，我们设玩家起点、阻碍者起点、终点分别为 \(s\)、\(e\) 和 \(t\)，计算两点距离的函数为 \(dist(x, y)\)。

假设玩家从 \(s\) 到 \(t\) 的路径中会经过点 \(k\)，当且仅当 \(dist(e, k) <= dist(s, k)\)，即阻碍者起点与点 \(k\) 的距离小于等于玩家起点与点 \(k\) 的距离时，阻碍者可以在点 \(k\) 抓到玩家。

由于玩家到终点以及阻碍者到终点的路径存在公共部分 \(dist(k, t)\)，可推导出：

\(dist(e, k) + dist(k, t) <= dist(s, k) + dist(k, t)\)

即得证 如果一个阻碍者能够抓到玩家，那么该阻碍者必然不会比玩家更晚到达终点。

由于步长为 1，且移动规则为上下左右四联通方向，因此 \(dist(x, y)\)的实现为计算两点的曼哈顿距离。

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