Escape The Ghosts

Problem Statement

In this problem, you engage with a game resembling a simplified PAC-MAN, set on an infinite 2-D grid. The game begins with you at the origin (coordinate [0, 0]) and a target destination given by coordinates [xtarget, ytarget]. Throughout the grid, various ghosts are positioned, stated by the array ghosts, wherein each element [xi, yi] indicates the starting position of a specific ghost.

The objective is to move from the origin to the target without being intercepted by any ghost. Each entity—the players and the ghosts—has the option each turn to move one unit in one of the four cardinal directions (north, east, south, or west) or remain stationary. All movements occur simultaneously. A successful escape to the target occurs if you can arrive before any ghost can intercept you. Interception is defined as a ghost reaching your location on the grid at the same or an earlier time.

The output should be true if you can always reach the target before any ghost can potentially reach it or intercept you along the way; otherwise, it should be false.

Examples

Example 1

Input:

ghosts = [[1,0],[0,3]], target = [0,1]

Output:

true

Explanation:

You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot 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.

Constraints

• 1 <= ghosts.length <= 100
• ghosts[i].length == 2
• -104 <= xi, yi <= 104
• There can be multiple ghosts in the same location.
• target.length == 2
• -104 <= xtarget, ytarget <= 104

Approach and Intuition

The key to solving this problem lies in comparing the Manhattan distance (sum of the absolute differences of their Cartesian coordinates) from you at the starting point [0, 0] to the target [xtarget, ytarget] against the Manhattan distance from each ghost’s starting position ghosts[i] = [xi, yi] to the same target. The steps involved are:

1. Calculate the Manhattan distance from the origin [0, 0] to the target [xtarget, ytarget] which would be |xtarget| + |ytarget|.
2. For each ghost's starting position, calculate the Manhattan distance to the target. This can be computed as |xi - xtarget| + |yi - ytarget| for each ghost.
3. Compare the calculated distance of your path to the target with each of the ghosts' distances:
   • If any ghost's distance is less than or equal to yours, they can intercept or reach the target before or at the same time as you, making it unsafe or impossible for you to succeed in escaping. Hence, return false.
   • If all ghosts have greater distances to the target than you, it is always possible to reach the target safely before the ghosts can, so return true.

The constraints ensure the viability of straightforward calculations and comparisons for up to 100 ghosts, given that calculating distances and making a few hundred comparisons (at most) are quite feasible computationally within the resource limits typically found in such settings.

Solutions

class Solution {
    public boolean canEscape(int[][] specters, int[] destination) {
        int[] startPoint = new int[]{0, 0};
        for (int[] specter: specters)
            if (manhattanDistance(specter, destination) <= manhattanDistance(startPoint, destination))
                return false;
        return true;
    }

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