Sponsored
Sponsored
This approach calculates the Manhattan distance from the starting point (0,0) to the target for you, and for each ghost from their starting position to the target. You can only escape if your distance to the target is strictly less than every ghost's distance to the target, meaning you reach the destination before any ghost can get there.
Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).
1#include <vector>
2#include <cstdlib>
3
4using namespace std;
5
6class Solution {
7public:
8 bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
9 int playerDist = abs(target[0]) + abs(target[1]);
10 for (const vector<int>& ghost : ghosts) {
11 int ghostDist = abs(ghost[0] - target[0]) + abs(ghost[1] - target[1]);
12 if (ghostDist <= playerDist) {
13 return false;
14 }
15 }
16 return true;
17 }
18};This C++ code calculates the player's and each ghost's Manhattan distance to the target. The player can escape only if they can reach the target before any ghost.
This approach involves simulating every possible move for you and each ghost simultaneously. For each time step, move each entity towards the target or keep them in the same position if they're already there. This approach is generally inefficient but illustrates the problem space.
Time Complexity: O(n), where n is the number of ghosts. Space Complexity: O(1).
1public class Solution {
public bool BruteForceEscape(int[][] ghosts, int[] target) {
int playerDist = Math.Abs(target[0]) + Math.Abs(target[1]);
foreach (int[] ghost in ghosts) {
int ghostDist = Math.Abs(ghost[0] - target[0]) + Math.Abs(ghost[1] - target[1]);
if (ghostDist <= playerDist) {
return false;
}
}
return true;
}
}This C# function simplifies brute force by evaluating distances rather than simulating every possible move.