Leetcode # 2849. Determine if a Cell Is Reachable at a Given Time

Problem

https://leetcode.com/contest/weekly-contest-362/problems/determine-if-a-cell-is-reachable-at-a-given-time/

Testcases

Solution

1. 可以斜走 ⇒ x, y 方向可以同時用 1 秒拉近 1 單位距離
   ⇒ 從 (sx, sy) 到 (fx, fy) 的最小步數為 max(abs(fx – sx), abs(fy – sy))
2. 餘下的秒數 (t – 最小步數) > 0
   1. 來回走消耗 2k 秒
   2. 消耗掉 2k 時間後，還剩餘 1 秒：
      1. 有斜走 ⇒ 拆成縱和橫，消耗掉剩餘的 1 秒
      2. 無斜走 ⇒ 將[縱/橫]改為斜走，在消耗掉消耗掉剩餘的 1 秒將另外一個維度調整回來
         ex: [+1, 0] -> [+1, +1] + [0, -1]
      3. 2-2-1 和 2-2-2 需要 t >= 2
         ⇔ 起點和終點相同，但t為1時，return為False
         

Time Complexity: O(1)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
    min_seconds = max(abs(fx - sx), abs(fy - sy))
    return t == min_seconds or (t > min_seconds and t >= 2)

Last Updated on 2023/09/10 by A1go