LWC 73: 789. Escape The Ghosts

LWC 73: 789. Escape The Ghosts

Problem:

You are playing a simplified Pacman game. You start at the point (0, 0), and your destination is (target[0], target1). There are several ghosts on the map, the i-th ghost starts at (ghosts[i][0], ghostsi). 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.

Examples:

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. 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. 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.

思路： 最优策略：所有ghost都守候在target处，等你来。所以只要计算ghost的曼哈顿距离中最小的，与你到target处的距离进行比较即可。可参考证明：https://leetcode.com/problems/escape-the-ghosts/discuss/116678/Why-interception-in-the-middle-is-not-a-good-idea-for-ghosts

Java版本：

    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int INF = 0x3f3f3f3f;
        int min_ghost = INF;
        for (int[] g : ghosts) {
            int dx = Math.abs(g[0] - target[0]);
            int dy = Math.abs(g[1] - target[1]);
            min_ghost = Math.min(min_ghost, dx + dy);
        }
        int me = Math.abs(target[0]) + Math.abs(target[1]);
        return min_ghost > me;
    }

python版本：

class Solution(object):
    def escapeGhosts(self, ghosts, target):
        """
        :type ghosts: List[List[int]]
        :type target: List[int]
        :rtype: bool
        """
        dist = abs(target[0]) + abs(target[1])
        return all(dist < abs(target[0] - i) + abs(target[1] - j) for i, j in ghosts)