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

难度: Medium

给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。

在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你必须移动到任一与之前所处单元格相邻的单元格中。

如果你能在恰好 t 秒后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。

单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。

示例 1：

输入：sx = 2, sy = 4, fx = 7, fy = 7, t = 6
输出：true
解释：从单元格 (2, 4) 开始出发，穿过上图标注的单元格，可以在恰好 6 秒后到达单元格 (7, 7) 。

示例 2：

输入：sx = 3, sy = 1, fx = 7, fy = 3, t = 3
输出：false
解释：从单元格 (3, 1) 开始出发，穿过上图标注的单元格，至少需要 4 秒后到达单元格 (7, 3) 。 因此，无法在 3 秒后到达单元格 (7, 3) 。

提示：

1 <= sx, sy, fx, fy <= 10⁹
0 <= t <= 10⁹

Submission

运行时间: 29 ms

内存: 16.0 MB

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        x_diff = abs(sx - fx)
        y_diff = abs(sy - fy)
        max_diff = max(x_diff, y_diff)
        if max_diff == 0:
            return True if t != 1 else False
        return True if t >= max_diff  else False

Explain

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

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        # 计算起点和终点在x轴和y轴上的差的绝对值
        x_diff = abs(sx - fx)
        y_diff = abs(sy - fy)
        # 取x和y差的最大值，即为最短到达时间
        max_diff = max(x_diff, y_diff)
        # 如果起点和终点完全相同，且时间不为1秒
        if max_diff == 0:
            return True if t != 1 else False
        # 如果时间大于等于最短到达时间
        return True if t >= max_diff else False

Explore

在常规的曼哈顿距离（L1范数）中，计算两点之间的距离是通过取两点在x轴和y轴上差的绝对值之和。而无穷大范数（L∞范数）则是取两点在x轴和y轴上差的绝对值中的最大值。在本题的环境中，由于可以移动到周围任何一个相邻的8个单元格，无穷大范数提供了一个更准确的步数估计，即直接走到目标位置的最短路径，用户只需要走最大的那个坐标差即可直达目的地。

当起点和终点完全相同，即没有距离需要移动时，理论上在0秒时已处于目标位置。但如果要在恰好1秒后到达同一个位置，则需要离开该位置并在下一秒返回，这需要至少2秒（出去再回来）。因此，在这种情况下，如果时间恰好为1秒，是无法在起点进行有效移动后又恰好回到起点的。

确实需要考虑时间t和最短距离max_diff的奇偶性。因为从一个单元格到另一个单元格的每一步都可能改变其奇偶性（例如，从(0,0)到(1,1)是奇数步至奇数步，而从(0,0)到(1,2)是奇数步至偶数步），所以如果从起点到终点的最小步数max_diff与给定时间t的奇偶性不匹配，那么即使时间足够，也无法恰好在t秒后到达目标单元格。因此，除了`t >= max_diff`外，还应检查`t % 2 == max_diff % 2`，以确保他们的奇偶性相同，从而确保可以恰好在t秒后到达目标单元格。