EscapeTheGhosts [source code]
public class EscapeTheGhosts {
static
/******************************************************************************/
class Solution {
public boolean escapeGhosts(int[][] ghosts, int[] target) {
int my_distance = Math.abs (target[0]) + Math.abs (target[1]);
for (int[] ghost : ghosts) {
int ghost_distance = Math.abs (ghost[0] - target[0]) + Math.abs (ghost[1] - target[1]);
if (ghost_distance <= my_distance)
return false;
}
return true;
}
}
/******************************************************************************/
public static void main(String[] args) {
EscapeTheGhosts.Solution tester = new EscapeTheGhosts.Solution();
int[][][] inputs = {
{{1,9},{2,-5},{3,8},{9,8},{-1,3}}, {{8, -10}}, {{0}},
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int[][] ghosts = inputs[3 * i];
int[] target = inputs[3 * i + 1][0];
boolean ans = inputs[3 * i + 2][0][0] != 0, output = tester.escapeGhosts (ghosts, target);
System.out.printf ("%s -> %s, expected: %b\n",
Arrays.deepToString (ghosts) + " and [" + Printer.array (target) + "]\n" + printBoard (ghosts, target), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
static String printBoard (int[][] ghosts, int[] target) {
int t = target[0], b = target[0], l = target[1], r = target[1];
for (int[] ghost : ghosts) {
t = Math.min (t, ghost[0]);
b = Math.max (b, ghost[0]);
l = Math.min (l, ghost[1]);
r = Math.max (r, ghost[1]);
}
int R = b - t + 1, C = r - l + 1;
char[][] chs = new char[R][C];
chs[target[0] - t][target[1] - l] = 'T';
for (int[] ghost : ghosts)
chs[ghost[0] - t][ghost[1] - l] = 'x';
return Matrix.printMatrix (chs);
}
}
看起来不像是DFS穷搜的, 好像是有一个分析的过程在里面?
感觉这题没什么套路, 只能人逻辑套路; 最后实际上能够拦住我的, 只有一个ghost, 那么找到这一个ghost, 是关键;
我感觉好像就是比一个距离啊? 如果有ghost离终点比我近, 那么他可以直接在终点等我? 好像不一定, 他如果提前到, 可能要重新出去再进来;
而, 看了一下题目, 是may, 所以实际上还简化了, 也就是每一个iteration, ghost可以选择不动; 那这个就是比较距离了啊;
速度是4ms (NA);
editorial
Approach #1: Taxicab Distance [Accepted]
Intuition
The taxicab distance is the number of moves required to get from point A to point B in our grid. It is calculated as dist(A, B) = abs(A.x - B.x) + abs(A.y - B.y).
Let's say we start at S, the ghost starts at G, the target is T, and the ghost first meets us at X. This implies dist(G, X) <= dist(S, X), as the ghost must reach X before or at the time that we do.
Now, if the ghost travels from G to X and then to T, it will reach T at time dist(G, T) <= dist(G, X) + dist(X, T) <= dist(S, X) + dist(X, T). The first inequality is because of the triangle inequality that all distance metrics satisfy.
The above shows that it is at least as good for the ghost to just travel directly to the target: if it could reach us beforehand (at X), it will also reach us if it goes to X then to T, and then it would reach us if it just went directly to T.
Also, if the ghost goes directly to the target, then a necessary condition is clearly that we get to the target before the ghost.
Once we can make the assumption that all parties just go directly to the target in the shortest time possible, the problem is greatly simplified.
我不知道他们为什么搞这么复杂, 一个ghost如果距离target更近, 直接守株待兔不就行了吗;
Algorithm
Check that our (taxicab) distance to the target is smaller than the distance from any ghost to the target.
class Solution {
public boolean escapeGhosts(int[][] ghosts, int[] target) {
int[] source = new int[]{0, 0};
for (int[] ghost: ghosts)
if (taxi(ghost, target) <= taxi(source, target))
return false;
return true;
}
public int taxi(int[] P, int[] Q) {
return Math.abs(P[0] - Q[0]) + Math.abs(P[1] - Q[1]);
}
}
Why interception in the middle is not a good idea for ghosts.
Let’s say you always take the shortest route to reach the target because if you go a longer or a more tortuous route, I believe the ghost has a better chance of getting you.
Denote your starting point A, ghost’s starting point B, the target point C.
For a ghost to intercept you, there has to be some point D on AC such that AD = DB. Fix D. By triangle inequality, AC = AD + DC = DB + DC >= BC. What that means is if the ghost can intercept you in the middle, it can actually reach the target at least as early as you do. So wherever the ghost starts at (and wherever the interception point is), its best chance of getting you is going directly to the target and waiting there rather than intercepting you in the middle.
我反正就用守株待兔的方法来理解的;
后来仔细看了一下他这个, 他这个其实证明的是一个必要条件, 也就是假如ghost能吃到你, 那么他一定也可以直接在终点等你; 我的思路其实只是一个充分条件: 一个能在终点等你的ghost肯定能吃掉你, 但是这没有必要性;
不过我其实还是感觉没有这么复杂, 这题很intuitive的, 就是只要ghost先到, 你就玩完;
https://leetcode.com/problems/escape-the-ghosts/discuss/116511/Short-with-explanation-python
The best tactic for any ghost is to reach the target before pacman and block the exit.
Note that we do not require that any ghost reaches pacman (which will never happen on an infinite grid for a single ghost and be much harder to determine for multiple ghosts).
We only require that pacman can or cannot reach the target with optimal ghost strategy.
If any ghost has the same or lower distance to the target, then it can get there first and wait. Pacman cannot reach the target, although he would not necessarily be killed by a ghost.
If pacman is closer to the target than any ghost, he goes there along the most direct path.Since we are working on a 2D grid, distances are measured as Manhattan distance.
def escapeGhosts(self, ghosts, target):
target_dist = abs(target[0]) + abs(target[1])
for r, c in ghosts:
ghost_target = abs(target[0] - r) + abs(target[1] - c)
if ghost_target <= target_dist:
return False
return True
大概意思是差不多的;
The best tactic for any ghost is to reach the target before pacman and block the exit.
why is this so? it isn’t obvious. if the ghost is nearer to your original location, then wouldn’t it be better for it to block you at origin? how does the “if and only if” part of this proposition hold?
原来这帮人是这样想的;
另外, 这个距离叫 Manhattan distance, 另外那个好像是Euclidean distance;
没有submission;
Problem Description
You are playing a simplified Pacman game. You start at the point (0, 0), and your destination is (target[0], target[1]). There are several ghosts on the map, the i-th ghost starts at (ghosts[i][0], ghosts[i][1]).
Each turn, you and all ghosts simultaneously may move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.
You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.) If you reach any square (including the target) at the same time as a ghost, it doesn't count as an escape.
Return True if and only if it is possible to escape.
Example 1:
Input:
ghosts = [[1, 0], [0, 3]]
target = [0, 1]
Output: true
Explanation:
You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.
Example 2:
Input:
ghosts = [[1, 0]]
target = [2, 0]
Output: false
Explanation:
You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.
Example 3:
Input:
ghosts = [[2, 0]]
target = [1, 0]
Output: false
Explanation:
The ghost can reach the target at the same time as you.
Note:
- All points have coordinates with absolute value <= 10000.
- The number of ghosts will not exceed 100.
Difficulty:Medium
Total Accepted:794
Total Submissions:2.1K
Contributor:awice