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/
是因為沒有買高級會員嗎？