789. Escape The Ghosts

发表于 | 分类于 | |

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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
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:

1
2
3
4
5
6
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 表示鬼魂的位置，玩家可以向上下左右进一步，求是否能在不遇到鬼魂的情况下，到达目标位置。

解题思路

根据以起点到目标位置的 曼哈顿距离记为 min_ghost，求是否有鬼魂的曼哈顿距离小于 min_ghost, 如果有则返回 true，否则返回 false。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func escapeGhosts(_ ghosts: [[Int]], _ target: [Int]) -> Bool {
        func manhattanDistance(lhs: [Int], rhs: [Int]) -> Int {
            return abs(lhs[0] - rhs[0]) + abs(lhs[1] - rhs[1])
        }
        
        var min_ghost = manhattanDistance(lhs: [0, 0], rhs: target)
        for point in ghosts {
            if manhattanDistance(lhs: point, rhs: target) <= min_ghost {
                return false
            }
        }
        return true
    }
}
0%