789. Escape The Ghosts

1. Question

You are playing a simplified PAC-MAN game on an infinite 2-D grid. You start at the point [0, 0], and you are given a destination point target = [xtarget, ytarget], which you are trying to get to. There are several ghosts on the map with their starting positions given as an array ghosts, where ghosts[i] = [xi, yi] represents the starting position of the ith ghost. All inputs are integral coordinates.

Each turn, you and all the ghosts may independently choose to either move 1 unit in any of the four cardinal directions: north, east, south, or west or stay still. All actions happen simultaneously.

You escape if and only if you can reach the target before any ghost reaches you. If you reach any square (including the target) at the same time as a ghost, it does not count as an escape.

Return true if it is possible to escape, otherwise return false.

2. Examples

Example 1:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot 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.

Example 4:

Input: ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]], target = [7,7]
Output: false

Example 5:

Input: ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]], target = [0,0]
Output: true

3. Constraints

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • -104 <= xi, yi <= 104
  • There can be multiple ghosts in the same location.
  • target.length == 2
  • -104 <= xtarget, ytarget <= 104

4. References

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/escape-the-ghosts 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

5. Solutions

只要比ghost更快到达终点就成了

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int n = Math.abs(target[0]) + Math.abs(target[1]);
        int m = ghosts.length;
        for (int i = 0; i < m; i++) {
            int a = Math.abs(target[0] - ghosts[i][0]) + Math.abs(target[1] - ghosts[i][1]) - n;
            if (a <= 0) {
                return false;
            }
        }
        return true;
    }
}
Copyright © rootwhois.cn 2021-2022 all right reserved,powered by GitbookFile Modify: 2022-11-26 20:03:31

results matching ""

    No results matching ""