判断能否在给定时间到达单元格

You are given four integers sx, sy, fx, fy, and a non-negative integer t.

In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.

Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.

A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.

 

Example 1:

Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6
Output: true
Explanation: Starting at cell (2, 4), we can reach cell (7, 7) in exactly 6 seconds by going through the cells depicted in the picture above. 

Example 2:

Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3
Output: false
Explanation: Starting at cell (3, 1), it takes at least 4 seconds to reach cell (7, 3) by going through the cells depicted in the picture above. Hence, we cannot reach cell (7, 3) at the third second.

 

Constraints:

• 1 <= sx, sy, fx, fy <= 109
• 0 <= t <= 109

/*
 * 题目思路：
 * 与普通Java解法一致，只是使用Java Stream进行更简洁的代码书写。
 * 计算最小步数和是否能在t秒内到达。
 */
import java.util.stream.IntStream;

public class Solution {
    public boolean isReachable(int sx, int sy, int fx, int fy, int t) {
        return IntStream.of(Math.abs(fx - sx), Math.abs(fy - sy))
                        .max()
                        .orElse(0) <= t && (t - IntStream.of(Math.abs(fx - sx), Math.abs(fy - sy)).max().orElse(0)) % 2 == 0;
    }
}

此题解的核心思路是计算起点(sx, sy)到终点(fx, fy)的最短距离，并判断该距离与给定时间t的关系。在一个无限的二维网格中，每次可以移动到周围8个相邻的单元格中的任意一个，因此最短路径是从起点到终点沿着对角线或直线的最大坐标差（即曼哈顿距离的变体，但使用的是无穷大范数而非L1范数）。解题关键是计算横纵坐标的差的绝对值，然后取这两者中的较大值max_diff作为到达目标所需要的最小步数。因为每一步都可以移动到任意相邻的单元格，只要时间t大于或等于max_diff，并且起点终点不是相同的单元格且t不等于1（因为从一个点出发一秒后不能回到原点），就可以在恰好t秒到达目标单元格。

O(1)

O(1)