[LeetCode] 2849. Determine if a Cell Is Reachable at a Given Time

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

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

给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。
在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你 必须 移动到任一与之前所处单元格相邻的单元格中。
如果你能在 恰好 t 秒 后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。
单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。

思路

这道题乍一看用 BFS 或者 DFS 做，但是注意题目规定相同单元格是可以访问多次的，如果 t 非常大，那么一定会超时。此时我们需要考虑别的做法。
正确的思路是判断起点到终点的绝对距离是否小于等于 t。注意这里绝对距离的意思是起点和终点的横坐标的绝对值的差和纵坐标的绝对值的差的较大值。如果这个绝对距离小于等于 t，说明在 t 时间内，一定能从起点走到终点，无非是需要在哪里绕圈圈以把时间消耗完。同时注意这道题允许我们往八个方向走，如果斜着往右上方走一步，其实是可以被拆解成往右一步和往上一步的，所以这里只要时间足够，步数总是可以被合法拆解的。

复杂度

时间O(n)
空间O(1)

代码

Java实现

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;
    }
}