789. Escape The Ghosts

You are playing a simplified Pacman game. You start at the point `(0, 0)`, and your destination is` (target[0], target[1])`. There are several ghosts on the map, the i-th ghost starts at` (ghosts[i][0], ghosts[i][1])`.

Each turn, you and all ghosts simultaneously may move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.)  If you reach any square (including the target) at the same time as a ghost, it doesn’t count as an escape.

Return True if and only if it is possible to escape.

``````Example 1:
Input:
ghosts = [[1, 0], [0, 3]]
target = [0, 1]
Output: true
Explanation:
You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.

Example 2:
Input:
ghosts = [[1, 0]]
target = [2, 0]
Output: false
Explanation:
You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3:
Input:
ghosts = [[2, 0]]
target = [1, 0]
Output: false
Explanation:
The ghost can reach the target at the same time as you.
``````

Note:

• All points have coordinates with absolute value <= `10000`.
• The number of ghosts will not exceed `100`.

``````class Solution {
public:
bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
int dist = abs(target[0]) + abs(target[1]), mn = INT_MAX;
for (auto ghost : ghosts) {
int t = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]);
mn = min(mn, t);
}
return dist < mn;
}
};
``````

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/789

https://leetcode.com/problems/escape-the-ghosts/

https://leetcode.com/problems/escape-the-ghosts/discuss/116507/Java-5-liner

https://leetcode.com/problems/escape-the-ghosts/discuss/116522/C%2B%2BJavaPython-Easy-and-Concise-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation