LeetCode 筆記 - 2849. Determine if a Cell Is Reachable at a Given Time

Posted on

題目在此 2849. Determine if a Cell Is Reachable at a Given Time

給定兩組座標開始與終點與時間，請問是否可以在剛好那個時間抵達終點。

每個時間單位可以移動一格，並且可以移動相鄰的 8 格，最重要的一點是地圖是無限大的，而且走過的格子可以重複走。

解題思維

名詞解說：

這題條件這麼寬鬆，其實就是需要思維轉一個彎，千萬不要看到座標、路徑就想到 DFS，這題 DFS 絕對會超時。
仔細想想，你會發現其實只要判斷終點是否在起點的 8 格內，且時間大於等於兩點的距離，就可以了。
因為我可以透過直走或斜走還有各種重複走，把時間控制在剛好那個時間就可以了。
剩下就是排除掉特殊情況，例如起點與終點相同但時間是一秒。image 106

程式碼

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:

        if fx == sx and fy == sy and t == 1:
            return False

        step = max(abs(fx - sx), abs(fy - sy))

        if t < step:
            return False
        return True
image 106

也許你也會想看看