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

给你四个整数 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 <= 109
• 0 <= t <= 109

请看 视频讲解 第二题。

由于可以往 8 个方向走，那么最快可以在

\max{|sx-fx|, |sy-fy|}

秒后到达终点（先斜着走再直走）。

上式只要小于等于 t 就能恰好到达终点。因为我们可以在到达终点附近时，在终点周围不断「绕圈」消耗时间，这样可以直到最后一秒才走到终点。

特殊情况：如果起点和终点重合，那么 t=1 的情况是无法回到起点的；如果 t\ne 1，我们可以同样地在起点不断「绕圈」，最后回到起点。

[sol-Python3]

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        if sx == fx and sy == fy:
            return t != 1
        return max(abs(sx - fx), abs(sy - fy)) <= t

[sol-Java]

public class Solution {
    public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy) {
            return t != 1;
        }
        return Math.max(Math.abs(sx - fx), Math.abs(sy - fy)) <= t;
    }
}

[sol-C++]

class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        if (sx == fx && sy == fy)
            return t != 1;
        return max(abs(sx - fx), abs(sy - fy)) <= t;
    }
};

[sol-Go]

func isReachableAtTime(sx, sy, fx, fy, t int) bool {
	if sx == fx && sy == fy {
		return t != 1
	}
	return max(abs(sx-fx), abs(sy-fy)) <= t
}

func abs(x int) int { if x < 0 { return -x }; return x }
func max(a, b int) int { if b > a { return b }; return a }

[sol-JavaScript]

var isReachableAtTime = function(sx, sy, fx, fy, t) {
    if (sx === fx && sy === fy) {
        return t !== 1;
    }
    return Math.max(Math.abs(sx - fx), Math.abs(sy - fy)) <= t;
};

复杂度分析

• 时间复杂度：\mathcal{O}(1)。
• 空间复杂度：\mathcal{O}(1)。

思考题

如果改成只能往 4 个方向走呢？