Formatted question description: https://leetcode.ca/all/789.html

789. Escape The Ghosts

Level

Medium

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.

Solution

The player starts at the point (0, 0) and the destination is (target[0], target[1]). The player can escape if and only if the player can reach the destination before any ghost. If there exists a ghost that can reach the destination at the same time as the player or earlier than the player, then the player can’t escape.

Since each move can be only in one of four cardinal directions, the number of moves required is calculated as the Manhattan distance. Calculate the distance between the player’s start point and the destination, and calculate the distances between each ghost’s point and the destination. If all the ghosts’ distances are greater than the player’s distance, return true. Otherwise, return false.

Why only consider the destination, not consider the case that a ghost reaches the player before the destination? The reason is that if a ghost’s distance to the destination is greater than the player’s distance to the destination, then as long as the player moves toward the destination, the ghost’s distance to the destination is always greater than the player’s distance to the destination, so it is impossible that the ghost and the player meet at the same point.

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int[] source = {0, 0};
        int distance = manhattanDistance(source, target);
        for (int[] ghost : ghosts) {
            int ghostDistance = manhattanDistance(ghost, target);
            if (ghostDistance <= distance)
                return false;
        }
        return true;
    }

    public int manhattanDistance(int[] source, int[] target) {
        return Math.abs(source[0] - target[0]) + Math.abs(source[1] - target[1]);
    }
}

// OJ: https://leetcode.com/problems/escape-the-ghosts/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& G, vector<int>& T) {
        int target = abs(T[0]) + abs(T[1]);
        for (auto &g : G) {
            if (abs(g[0] - T[0]) + abs(g[1] - T[1]) <= target) return false;
        }
        return true;
    }
};

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        tx, ty = target
        return all(abs(tx - x) + abs(ty - y) > abs(tx) + abs(ty) for x, y in ghosts)

############

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

func escapeGhosts(ghosts [][]int, target []int) bool {
	tx, ty := target[0], target[1]
	for _, g := range ghosts {
		x, y := g[0], g[1]
		if abs(tx-x)+abs(ty-y) <= abs(tx)+abs(ty) {
			return false
		}
	}
	return true
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

function escapeGhosts(ghosts: number[][], target: number[]): boolean {
    const [tx, ty] = target;
    for (const [x, y] of ghosts) {
        if (
            Math.abs(tx - x) + Math.abs(ty - y) <=
            Math.abs(tx) + Math.abs(ty)
        ) {
            return false;
        }
    }
    return true;
}

789 - Escape The Ghosts

789. Escape The Ghosts

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

789. Escape The Ghosts

Level

Description

Solution

All Problems

All Solutions