grid47 Exploring patterns and algorithms
Aug 20, 2024
6 min read
Solution to LeetCode 789: Escape The Ghosts Problem
You are playing a simplified game on an infinite 2-D grid where you start at position [0, 0], and your goal is to reach a destination point target = [xtarget, ytarget]. There are several ghosts on the map, each with its starting position. You and the ghosts can all independently move one unit in any of the four cardinal directions (north, east, south, or west), or stay still. If you can reach the destination before any ghost catches up with you, you escape. You cannot escape if you reach any square at the same time as a ghost. Your task is to return true if it is possible to escape, otherwise return false.
Problem
Approach
Steps
Complexity
Input: You are given the positions of ghosts and a target point. The ghosts' positions are provided as a 2D array, and the target point is also given as an array of two integers.
• Explanation: In this example, the target [0, 1] can be reached in 1 move, and both ghosts at positions [1, 0] and [0, 3] cannot catch up before you. Hence, the output is true.
• Input: Input: ghosts = [[1,0]], target = [2,0]
• Explanation: In this case, the ghost at position [1, 0] can reach the target at the same time you do, preventing you from escaping. Thus, the output is false.
• Explanation: Here, the ghost can reach the target at the same time as you, so escape is not possible, resulting in false.
Approach: We can calculate the Manhattan distance from the start point to the target and compare it to the distances of the ghosts to the target. If any ghost can reach the target before or at the same time as you, you cannot escape.
Observations:
• We need to check the distance between each ghost and the target and compare it to your distance to the target.
• The problem can be reduced to a simple check of whether the ghost's distance is greater than yours to the target. If a ghost is closer or the same distance, you cannot escape.
Steps:
• Calculate the Manhattan distance from [0, 0] to the target.
• For each ghost, calculate its Manhattan distance to the target.
• If any ghost has a distance less than or equal to yours, return false.
• Otherwise, return true.
Empty Inputs:
• There are no empty inputs, as the number of ghosts is always at least 1.
Large Inputs:
• Handle cases where the number of ghosts is large (up to 100) by ensuring the solution is efficient.
Special Values:
• If ghosts are located at the same position as the target, you will not escape.
Constraints:
• Ensure that the ghost positions and target coordinates are within the specified constraints.
The function 'escapeGhosts' is defined with two parameters: 'gs', a vector of ghost positions, and 't', a vector representing Pac-Man's target position.
2 : Distance Calculation
int d = abs(t[0]) + abs(t[1]);
This line calculates the Manhattan distance from Pac-Man's current position to the target position 't'. The absolute values of the differences in the x and y coordinates are added.
3 : Loop Through Ghosts
for(autoit: gs)
A for-each loop is used to iterate over each ghost's position in the 'gs' vector.
4 : Distance Comparison
if(d >= abs(it[0] - t[0]) + abs(it[1] - t[1]))
For each ghost, this condition checks if Pac-Man's travel distance 'd' is greater than or equal to the ghost's distance from Pac-Man. If so, it means the ghost can potentially catch Pac-Man.
5 : Return False
returnfalse;
If the condition is true, meaning a ghost can catch Pac-Man, the function returns 'false', indicating Pac-Man cannot escape.
6 : Return True
returntrue;
If no ghosts can catch Pac-Man, the function returns 'true', indicating Pac-Man can escape.
Best Case: O(g), where g is the number of ghosts.
Average Case: O(g), since we check each ghost once.
Worst Case: O(g), where g is up to 100.
Description: The time complexity is linear with respect to the number of ghosts since we calculate the distance for each ghost and compare it to your own.
Best Case: O(1), if no extra space is required apart from input data.
Worst Case: O(g), where g is the number of ghosts (for storing their positions).
Description: The space complexity is linear in the number of ghosts because we need to store their positions.
