This is the 22nd day of my participation in the August More Text Challenge

789. Escape from obstructors

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
  • -10^4 <= xi, yi <= 10^4
  • There can be multiple obstructors in the same location.
  • target.length == 2
  • -104 <= xtarget, ytarget <= 104

Methods a

If the obstructionist can stop me on the way to or at the end of my journey, I will escape failure. The initial thought was that if obstructionists could take a detour and stop me on the way, they could just go to the finish line and wait for me to be caught. Therefore, the first method is to draw a circle at the end point with the radius of the end point and the starting point. If there is an obstacle in the circle or on the circle, then escape failure, otherwise, success; But this has only been done in 51/77 cases;

On the wrong sample analysis, found the problem, because coordinates are integers, so there will be a problem, for example, the finish is (0, 0), and I in (5, 5), there was a block in (4, 6), the circle is not, but gets only need 10 steps to reach the finish line, so the Manhattan distance, the sum of the absolute value of horizontal ordinate is poor;

class Solution { public boolean escapeGhosts(int[][] ghosts, int[] target) { double r = Math.abs(target[0]) + Math.abs(target[1]); for (int[] iter : ghosts) { double d = Math.abs(target[0] - iter[0]) + Math.abs(target[1] - iter[1]); if (d <= r) return false; } return true; }}Copy the code