Problem Explanation

In this problem, you are in a game where your character (we'll call it Pacman) is initially at position (0, 0). Pacman's goal is to reach a target point determined by an input array target = [x, y]. However, there are ghosts on the map that might prevent Pacman from reaching the target. Each ghost's initial position is determined by a sub-array in an input 2D array ghosts = [[x1, y1], [x2, y2], ..., [xn, yn]]. On each turn, Pacman and the ghosts can move one unit in any of the four cardinal directions (north, east, south, west). If a ghost reaches Pacman before Pacman reaches the target, or a ghost reaches the same place as Pacman at the same time, Pacman loses. Otherwise, Pacman successfully escapes.

Walkthrough

Let's walk through an example to understand how we can solve this problem:

Example Input:

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

The Manhattan Distance (distance travelled in the four cardinal directions) from Pacman's starting point to the target is abs(0 - 0) + abs(1 - 0) = 1. Meanwhile, the closest ghost to the target is at position [1, 0], and the distance from this ghost to the target is abs(1 - 0) + abs(0 - 1) = 2. Since the ghost at [1, 0] cannot reach the target before Pacman does, Pacman can successfully escape, so the function should return true.

Approach

The solution to this problem is actually simple: to determine if Pacman can escape, we just need to check if Pacman can reach the target before any ghost can. This can be achieved by comparing the Manhattan Distance from Pacman's starting position to the target and the Manhattan Distance from each ghost's starting position to the target. If any ghost can reach the target before or at the same time as Pacman, the function should return false. Otherwise, it should return true.

Solutions

Python

1
2python
3class Solution:   
4    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
5        manhattan_distance = abs(target[0]) + abs(target[1])
6        for ghost in ghosts:
7            if manhattan_distance >= abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]):
8                return False
9        return True  

Java

1
2java
3class Solution {
4    public boolean escapeGhosts(int[][] ghosts, int[] target) {
5        int manhattanDistance = Math.abs(target[0]) + Math.abs(target[1]);
6        for (int[] ghost : ghosts) {
7            if (manhattanDistance >= Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1])) {
8                return false;
9            }
10        }
11        return true;
12    }
13}

JavaScript

1
2javascript
3class Solution {
4    escapeGhosts(ghosts, target) {
5        let manhattanDistance = Math.abs(target[0]) + Math.abs(target[1]);
6        for (let ghost of ghosts) {
7            if (manhattanDistance >= Math.abs(ghost[0] - target[0]) + Math.abs(ghost[1] - target[1])) {
8                return false;
9            }
10        }
11        return true;
12    }
13}

C++

1
2c++
3class Solution {
4public:
5    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
6        int manhattanDistance = abs(target[0]) + abs(target[1]);
7        for (vector<int>& ghost : ghosts) {
8            if (manhattanDistance >= abs(ghost[0] - target[0]) + abs(ghost[1] - target[1])) {
9                return false;
10            }
11        }
12        return true;
13    }
14};

C#

1
2csharp
3public class Solution {
4    public bool EscapeGhosts(int[][] ghosts, int[] target) {
5        int manhattanDistance = Math.Abs(target[0]) + Math.Abs(target[1]);
6        foreach (int[] ghost in ghosts) {
7            if (manhattanDistance >= Math.Abs(ghost[0] - target[0]) + Math.Abs(ghost[1] - target[1])) {
8                return false;
9            }
10        }
11        return true;
12    }
13}

Explanation of the Code

In each solution, we first calculate the Manhattan Distance from Pacman's starting position (0, 0) to the target.

Then, we go through each sub-array (which represents the coordinates of a ghost) in the ghosts array. For each ghost, we calculate the Manhattan Distance from the ghost's position to the target.

If the Manhattan Distance of any ghost is less than or equal to the Manhattan Distance of Pacman, we know that the ghost can reach the target point before or at the same time as Pacman. Therefore, Pacman cannot escape successfully, and we return false.

If after checking all the ghosts no such ghost is found, we know that Pacman can reach the target before all the ghosts. Therefore, Pacman can successfully escape, and we return true.The solutions provided solve the problem in O(n) time complexity, where n is the number of ghosts. This is because we perform a single iteration over the array of ghosts. Therefore, the time complexity of the solution is proportional to the number of ghosts.

In terms of space complexity, our solutions only use a constant amount of space to store the Manhattan Distance for Pacman and each ghost. Thus, our solutions have O(1) space complexity.

These solutions are efficient, and solve the problem as expected. However, one should always remember that the Manhattan Distance used in these solutions is applicable because the movement is restricted to the four cardinal directions (north, east, south, and west). If the movement weren't restricted in this manner, we would need to use a different distance calculation method, such as the Euclidean Distance.

As a final note, understanding the nature of the problem and the restrictions in place allows for a quicker realization that the problem can be solved using the concept of Manhattan Distance, further enhancing problem-solving skills and efficiency.

In conclusion, this game-inspired problem is a great example of how understanding the rules and constraints can simplify the problem-solving process. It demonstrates the power of the Manhattan Distance metric in the context of grid-based games and highlights the importance of interpreting a problem correctly to identify the optimal solution.