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^9
  • 0 <= t <= 10^9

解题思路

这道题的核心是计算从起点到终点的最短时间，以及判断是否能在恰好 t 秒时到达目标。

首先分析最短路径时间。由于可以向8个方向移动，这相当于国际象棋中王的移动方式。从 (sx, sy) 到 (fx, fy) 的最短时间是切比雪夫距离，即：max(|fx - sx|, |fy - sy|)。

关键分析：

  1. 如果起点和终点相同 (sx == fx && sy == fy)：

    • 若 t == 0，返回 true
    • 若 t == 1，返回 false（因为必须移动，但下一秒无法回到原点）
    • 若 t >= 2，返回 true（可以来回移动浪费时间）

  2. 如果起点和终点不同：

    • 若 t 小于最短时间，返回 false
    • 若 t 大于等于最短时间，需判断剩余时间的奇偶性
    • 剩余时间必须是偶数才能通过来回移动消耗掉

因为每次移动都会改变曼哈顿距离的奇偶性，所以只有当剩余时间为偶数时，才能恰好在 t 秒到达目标。

代码实现

class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int dx = abs(fx - sx);
        int dy = abs(fy - sy);
        
        // 特殊情况：起点和终点相同
        if (dx == 0 && dy == 0) {
            return t != 1;
        }
        
        // 计算最短时间（切比雪夫距离）
        int minTime = max(dx, dy);
        
        // 时间不足
        if (t < minTime) {
            return false;
        }
        
        // 剩余时间必须是偶数
        return (t - minTime) % 2 == 0;
    }
};

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        dx = abs(fx - sx)
        dy = abs(fy - sy)
        
        # 特殊情况：起点和终点相同
        if dx == 0 and dy == 0:
            return t != 1
        
        # 计算最短时间（切比雪夫距离）
        min_time = max(dx, dy)
        
        # 时间不足
        if t < min_time:
            return False
        
        # 剩余时间必须是偶数
        return (t - min_time) % 2 == 0

public class Solution {
    public bool IsReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int dx = Math.Abs(fx - sx);
        int dy = Math.Abs(fy - sy);
        
        // 特殊情况：起点和终点相同
        if (dx == 0 && dy == 0) {
            return t != 1;
        }
        
        // 计算最短时间（切比雪夫距离）
        int minTime = Math.Max(dx, dy);
        
        // 时间不足
        if (t < minTime) {
            return false;
        }
        
        // 剩余时间必须是偶数
        return (t - minTime) % 2 == 0;
    }
}

var isReachableAtTime = function(sx, sy, fx, fy, t) {
    const dx = Math.abs(fx - sx);
    const dy = Math.abs(fy - sy);
    
    if (dx === 0 && dy === 0) {
        return t !== 1;
    }
    
    const minTime = Math.max(dx, dy);
    return t >= minTime;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(1)
空间复杂度O(1)

相关题目