题目描述：

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

题目大意：

玩家从原点出发到达目标位置target，每次可以向上下左右任意方向移动一步。

给定一些鬼魂的位置ghosts，判断是否可以在不遇到鬼魂的情况下到达目标位置。

解题思路：

曼哈顿距离（Manhattan Distance ）

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

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

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

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

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

Python代码：

class Solution(object):
    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)

 

本文链接：http://bookshadow.com/weblog/2018/02/25/leetcode-escape-the-ghosts/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码