Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

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/

是因為沒有買高級會員嗎？

--
                                                                    Zoosewu
                              Yoututbe顯示PTT推文
                       可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png https://i.imgur.com/WqbLNV3.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699415969.A.C2B.html
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/08/2023 11:59:53
推 sustainer123: 大師
推 SecondRun: 最近好多邏輯比演算法重要的題目
推 oin1104: 大師 我等等也來寫寫看
→ ZooseWu: 恩 我蠻喜歡這種算法不難 重點是理解題意找到解法的
推 NTHUlagka: 大師
→ Rushia: solution那邊可以PO文章