题目大意：给你目的地坐标以及幽灵的坐标，初始点在(0,0)，每次你和幽灵都可以移动一步。问你是否可以安全到达终点。
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.
|
1 2 3 4 5 6 7 |
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. |
|
1 2 3 4 5 6 7 |
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. |
|
1 2 3 4 5 6 7 |
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.
Solution: Greedy / Math
You can escape if and only if no ghosts can reach target before you. Just need to compare the Manhattan distance.
如果所有的幽灵都无法在你之前到达target，那么你可以逃脱。只要比较曼哈顿距离即可。
C++
Time complexity: O(|ghost|)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 4 ms class Solution { public: bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) { const int steps = abs(target[0]) + abs(target[1]); for (const auto& g: ghosts) if (abs(g[0] - target[0]) + abs(g[1] - target[1]) <= steps) return false; return true; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua // Running time: 4 ms class Solution { public boolean escapeGhosts(int[][] ghosts, int[] target) { final int steps = Math.abs(target[0]) + Math.abs(target[1]); for (int[] g : ghosts) if (Math.abs(g[0] - target[0]) + Math.abs(g[1] - target[1]) <= steps) return false; return true; } } |
Python3
|
1 2 3 4 5 6 7 8 |
""" Author: Huahua Running time: 40 ms """ class Solution: def escapeGhosts(self, ghosts, target): steps = abs(target[0]) + abs(target[1]) return not any(abs(x - target[0]) + abs(y - target[1]) <= steps for x, y in ghosts) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment