2849. Determine if a Cell Is Reachable at a Given Time
在一个无限大的二维网格中
你从start(sx,sy)开始每秒移动到邻近格子
如果你能在第t秒的时候待在finish(fx,fy)则回传true
否则回传false
* 邻近格子代表相邻的八格，允许走到已经走过的格子
例题:
Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6
Output: true
从(2,4)开始[右,右,右,右下,下,右下]可以到达终点(7,7)
https://assets.leetcode.com/uploads/2023/08/05/example2.svg
Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3
Output: false
最短需要四秒才能到达
https://assets.leetcode.com/uploads/2023/08/05/example1.svg
Intuition:
题目不只能走上下左右
而是相邻的八格都能移动
所以走的方法很自由
重点在于有没有办法在时限内到终点
Approach:
这题的起点座标跟终点座标完全不重要
重要的是两个座标之间的水平距离dx以及垂直距离dy。
根据题目描述我们移动能选择邻近八格
这代表我们从起点开始花费四步能走到下图中所有紫色的格子：
https://i.imgur.com/zRGHyqj.png
同理绿色是两步能到达的位置、青色三步
因此我们可以知道走到终点最少需要的步数是dx及dy取大值。
但是题目的要求不是有没有办法在t步以内走到
而是有没有办法在第t步时待在目标格子中
我们可以透过下面的方法
让我们的步数增加到在第t步的时候待在终点：
如果目标步数跟最短步数差一格的话
我们可以把往横一步改成往斜一步再往直回来
往斜同理可以换成往横后再往直
让一步变成两步 像是下图这样：https://i.imgur.com/blQYdKt.png
如果差超过两格的话
就来回走动直到结束或只差一步
然后用上面的方法到终点
例如下图就是透过上面的方法用不同步数从红色到蓝色的范例路径：
https://i.imgur.com/jnOYkfP.png
所以任何t大于最低所需步数的情况我们都不用考虑
只要判断能不能在时限内到终点就好
这题我原本以为到这边就结束了
提交后报错才发现这个边界案例dx = dy = 0, t = 1
是唯一没办法透过上面的方法去达到终点的状况
TS Code:
function isReachableAtTime (sx: number, sy: number, fx: number, fy: number,
t: number): boolean {
const [dx, dy] = [Math.abs(fx - sx), Math.abs(fy - sy)]
if ((dx + dy) === 0 && t === 1) return false
return Math.max(dx, dy) <= t
};
C# Code:
public class Solution
{
public bool IsReachableAtTime(int sx, int sy, int fx, int fy, int t)
{
int dx = Math.Abs(fx - sx), dy = Math.Abs(fy - sy);
if ((dx + dy) == 0 && t == 1) return false;
return Math.Max(dx, dy) <= t;
}
}
另外请教LeetCode大师
为什么我写的文章别人都看不到
只有我自己看的到？
https://leetcode.com/Zoosewu/
是因为没有买高级会员吗？