This is the 22nd day of my participation in the August Wen Challenge.More challenges in August

Topic describes

This is 789 on LeetCode. Escape obstructionist, medium difficulty.

Tag: math

You’re playing a simplified version of Pac-Man. You start at [0, 0] and your destination is target = [xtarget, ytarget]. There are some obstructors on the map, given by the array ghosts. The ith obstructor starts from 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:

Ghosts = [[1,0],[0,3]], target = [0,1]Copy the code

Example 2:

Ghosts = [[1,0]], target = [2,0] Output: false Explanation: You need to go to the destination at (2, 0), but the obstructor at (1, 0) is between you and the destination.Copy the code

Example 3:

Ghosts = [[2,0]], target = [1,0]Copy the code

Example 4:

Input: ghosts = [[5, 0], [-, 10-2], [0, 5], [2, 2], [7, 1]], target = (7, 7] output: falseCopy the code

Example 5:

Input: ghosts = [[- 1, 0], [0, 1], [- 1, 0], [0, 1], [- 1, 0]], target = [0, 0] output: trueCopy the code

Tip:

  • 1 <= ghosts.length <= 100
  • ghosts[i].length == 2
  • –
    1 0 4 10^4     <= xi, yi <=
    1 0 4 10^4
  • There can be multiple obstructors in the same location.
  • target.length == 2
  • –
    1 0 4 10^4     <= xtarget, ytarget <=
    1 0 4 10^4

mathematics

−104<=xtarget,ytarget<=104-10^4 <= x_{target}, Y_ {target} <=10 ^4−104<=xtarget,ytarget<=104 and can move only one unit at a time (or not) is doomed to use naive BFS for solving.

Naive BFS means that every time the player moves a step, “grays” the position that the obstructionist can reach in one step (that is, set it to never reachable), and then determines whether the player can reach targettargettarget.

Naive BFS is essentially a simulation, and since the board is large enough to have a step size of only 111, it would obviously TLE.

Is there a faster way to do this than simulation?

From a proof like “Diameter of tree”, we can prove that “if an obstructionist can catch the player, he will not arrive later than the player”.

For convenience, we set the starting point of player, starting point of obstacle and end point as SSS, Eee and TTT respectively, and calculate the distance between two points as dist(x,y) Dist (x,y)dist(x, Y)dist(x, Y).

If and only if dist(e,k)<=dist(s,k)dist(e, k)<=dist(S,k)dist(e, k)<=dist(s,k) That is, “obstructor starting point and point KKK distance” is less than or equal to “player starting point and point KKK distance”, obstructors can catch players at point KKK.

Dist (k,t) Dist (k,t)dist(k, t)dist(k,t) exists in the paths of “player to end” and “obstructor to end”, it can be deduced that:


d i s t ( e . k ) + d i s t ( k . t ) < = d i s t ( s . k ) + d i s t ( k . t ) dist(e, k) + dist(k, t) <= dist(s, k) + dist(k, t)

If an obstructionist can catch the player, then that obstructionist must not arrive after the player.

Since the step size is 111 and the movement rule is four directions of up, down, left and right, dist(x,y) Dist (x,y) Dist (x,y)dist(x, y) is realized by calculating the Manhattan distance of two points.

Code:

class Solution {
    int dist(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
    public boolean escapeGhosts(int[][] gs, int[] t) {
        int cur = dist(0.0, t[0], t[1]);
        for (int[] g : gs) {
            if (dist(g[0], g[1], t[0], t[1]) <= cur) return false;
        }
        return true; }}Copy the code
  • Time complexity: Set GSGSGS length as NNN, calculate Manhattan distance complexity as O(1)O(1)O(1), and overall complexity as O(n)O(n)O(n) O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.789 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.