LeetCode 789 - Escape The Ghosts

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

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.

https://blog.csdn.net/huanghanqian/article/details/79368471

注意这道题是 all ghosts  *may* move in one of 4 directions ，也就是说，ghost 可以选择原地不动，也可以选择四个方向走一格。（实际上题目中的 example #2 就隐含了这一点，如果 ghost 必须移动的话， example #2 应该返回 true。）

我是这么想的，只要 “ghost与target之间的距离” 比 “我与target之间的距离” 近的话，ghost 一定能赢。因为 ghost 可以也一直往 target 前进，然后等候在 target 旁边，一直等到我最后一步跨入 target 时，跟我一起跨入 target，我就会被抓住。而如果 “ghost与target之间距离” 比 “我与target之间的距离” 远，只要我一直往 target 走，ghost 无论如何跟着我也抓不到我

大神的说法是：ghost 的最佳策略是，一直往 target 走，并且抢到玩家到达之前先抢占 target，这样玩家肯定输。因此，如果任何 “ghost 对于 target 的曼哈顿距离” 小于等于 “玩家对于 target 的曼哈顿距离”，那么玩家肯定会输。无论如何，大神跟我的解法都一样。

1. public boolean escapeGhosts(int[][] ghosts, int[] target) {  
2.     int myDistance=Math.abs(target[0])+Math.abs(target[1]);  
3.     for(int i=0;i<ghosts.length;i++){  
4.         int ghostDistance=Math.abs(target[0]-ghosts[i][0])+Math.abs(target[1]-ghosts[i][1]);  
5.         if(ghostDistance<=myDistance){  
6.             return false;  
7.         }  
8.     }  
9.         return true;  
10. }  

https://gist.github.com/oliverwreath/08be4fdfb7db1b3182ee135405f05071

    boolean escapeGhosts(int[][] ghosts, int[] target) {

        // filter abnormal cases

//        if (A == null || A.length == 0) {

//            return 0;

//        }

        if (ghosts == null || ghosts.length == 0) {

            return true;

        }

        int myDistance = getDistance(new int[]{0, 0}, target);

        int m = ghosts.length;

        for (int i = 0; i < m; i++) {

            int tmpDistance = getDistance(ghosts[i], target);

            if (tmpDistance <= myDistance) {

                return false;

            }

        }

        // return the final result

        return true;

    }

    int getDistance(int[] source, int[] target) {

        return Math.abs(source[0] - target[0]) + Math.abs(source[1] - target[1]);

    }

http://bookshadow.com/weblog/2018/02/25/leetcode-escape-the-ghosts/

曼哈顿距离（Manhattan Distance ）

判断是否存在鬼魂与目标位置的曼哈顿距离 <= 原点与目标位置的曼哈顿距离。

记原点为O，target为T；以T为圆心，OT为半径做圆。

从O开始沿半径到达T的路径最优（两点之间线段最短）。

若存在鬼魂的位置G在圆内，则鬼魂一定可以抢先到达T（ |GT| < |OT| ）。

圆外的鬼魂一定无法与玩家相遇，假设圆外的鬼魂从G'出发，与玩家在线段OT上的K点相遇，但显然 |KO| 始终小于 |KG'|，假设不成立。

def escapeGhosts(self, ghosts, target): """ :type ghosts: List[List[int]] :type target: List[int] :rtype: bool """ mht = sum(map(abs, target)) tx, ty = target return not any(abs(gx - tx) + abs(gy - ty) <= mht for gx, gy in ghosts)
https://leetcode.com/problems/escape-the-ghosts/discuss/116511/Short-with-explanation-python

The best tactic for any ghost is to reach the target before pacman and block the exit.

Note that we do not require that any ghost reaches pacman (which will never happen on an infinite grid for a single ghost and be much harder to determine for multiple ghosts).
We only require that pacman can or cannot reach the target with optimal ghost strategy.
If any ghost has the same or lower distance to the target, then it can get there first and wait. Pacman cannot reach the target, although he would not necessarily be killed by a ghost.
If pacman is closer to the target than any ghost, he goes there along the most direct path.

Since we are working on a 2D grid, distances are measured as Manhattan distance.

https://leetcode.com/problems/escape-the-ghosts/discuss/116678/Why-interception-in-the-middle-is-not-a-good-idea-for-ghosts.

Let's say you always take the shortest route to reach the target because if you go a longer or a more tortuous route, I believe the ghost has a better chance of getting you.
Denote your starting point A, ghost's starting point B, the target point C.
For a ghost to intercept you, there has to be some point D on AC such that AD = DB. Fix D. By triangle inequality, AC = AD + DC = DB + DC >= BC. What that means is if the ghost can intercept you in the middle, it can actually reach the target at least as early as you do. So wherever the ghost starts at (and wherever the interception point is), its best chance of getting you is going directly to the target and waiting there rather than intercepting you in the middle.