Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. Topic description

You’re playing a simplified version of Pac-Man. You start at point [0, 0] and your destination is target=[xtarget,ytarget]target =[x_target, y_target]target=[xtarget,ytarget]. Ghosts [I]=[xi,yi]ghosts[I]=[x_i, y_i]ghosts[I]=[xi,yi] All inputs are integer coordinates.

Each turn, you and your obstructors can move east, west, south, and north at the same time, moving 1 unit at a time. Of course, you can choose not to move. All at the same time.

If you can reach your destination before any obstructionist catches you (obstructionists can act in any way they want), you are considered a successful escape. It is not an escape if you and the obstructionist reach the same location (including the destination) at the same time.

Print true only if you are likely to escape successfully; Otherwise, print false.

Example 1: Input: ghosts = [[1, 0], [0, 3]] target = [0, 1] Output: true Explanation: you can get to destination (0,1) directly, obstructors at (1, 0) or (0, 3) will not catch you. Example 2: Input: ghosts = [[1, 0]] Target = [2, 0] Output: false Explanation: You need to walk to the destination at (2, 0), but the obstructor at (1, 0) is between you and the destination. Example 3: Input: ghosts = [[2, 0]] Target = [1, 0] Output: false Explanation: Obstructionist can reach the destination at the same time as you. Example 4: input: ghosts = [[5, 0], [-, 10-2], [0, 5], [2, 2], [7, 1]], target = (7, 7] output: false example 5: input: Ghosts = [[- 1, 0], [0, 1], [- 1, 0], [0, 1], [- 1, 0]], target = [0, 0] output: trueCopy the code

2.

For this problem, there may be some people will first build maps, and then wide search, deep search what, in fact, this problem is a mathematical problem. The best way for obstructors to catch you is to wait for you at the finish line. The mathematical proof is as follows: if the ghost is to intercept AC in the middle it must have a point D on it such that AD = DB, by using the triangle inequality AC = AD + DC = DB + DC >= BC. If a ghost can intercept it, it’s better for the ghost to wait at the end rather than in the middle. The choice above is the shortest path, disorderly walk, I believe that the ghost will laugh more happy!!

/** A represents the starting point, B represents the location of the ghost, and destination is C. * * C * / \ * / \ * / \ * / \ * / \D \ * / \ \ * / \ \ * / \ \ * A \ * B * * */Copy the code

The shortest distance you can reach target is abs(Target [0])+ ABS (target[1]), and the shortest distance you can reach target is ABS (Ghost [0]-target[0])+ ABS (Ghost [1]-target[1]). So we just have to compare the two.

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int myMindistance = abs(target[0]) + abs(target[1]);// The shortest distance I can reach the finish line
        for (auto &ghost : ghosts){// Determine if ghost got to the finish line before me
            if (myMindistance >= abs(ghost[0]-target[0])+abs(ghost[1]-target[1])){
                return false; }}return true; }};Copy the code

Complexity analysis

  • Time complexity: O(ghosts. Length)O(\text{ghosts}.\text{length})O(ghosts. Length)
  • Space complexity: O(1)O(1)O(1)

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream