判斷是否能在時間限制內抵達終點 Leetcode #2849
這題的題目在這裡:Determine if a Cell Is Reachable at a Given Time
題目敘述
題目會給定我們兩個點座標，分別是起點和終點。
另外，還有一個參數t，代表時間限制。
從起點出發之後，每一秒鐘，我們必須選擇一個N8 8連通的方向，往鄰居的格子點移動。(題目有特別強調，每一秒必須強制移動到下一個格子點，不能停留在原地)
註:
N8 8連通代表可以往東、南、西、北、東北、西北、東南、西南 選一個方向移動一格。
請問我們能不能在時間限制內，從起點走到終點?
測試範例
Example 1:
Input: sx = 2, sy = 4, fx = 7, fy = 7, t = 6
Output: true
Explanation: Starting at cell (2, 4), we can reach cell (7, 7) in exactly 6 seconds by going through the cells depicted in the picture above.
Example 2:
Input: sx = 3, sy = 1, fx = 7, fy = 3, t = 3
Output: false
Explanation: Starting at cell (3, 1), it takes at least 4 seconds to reach cell (7, 3) by going through the cells depicted in the picture above. Hence, we cannot reach cell (7, 3) at the third second.
約束條件
Constraints:
1 <= sx, sy, fx, fy <= 10^90 <= t <= 10^9
演算法
除了傳統的BFS + N8的路徑模擬演算法以外，其實，還可以使用Chebyshev distance來進行估計。
Chebyshev distance的定義就是兩個點座標，假設都沒有障礙物，在平面上N8 8連通走法的最短距離。
Chebyshev distance(x, y) = Max{ |x1-x2|, |y1-y2|}
從起點的視角來看，就像一個方形的同心紋路，一層一層，由內往外擴散
因為，每一秒鐘移動一步，所以，假如兩點的Chebyshev distance <= 限制t
則代表，從起點出發，用N8 8連通的走法，可以在時間限制t內抵達終點。
唯一有一個例外，要特別小心，當起點等於終點，而且t=1時，反而無法抵達，為什麼?
題目有特別強調，每一秒必須強制移動到下一個格子點，不能停留在原地。
所以，當起點等於終點，而且t=1時，必須return False
程式碼
class Solution:
def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
if sx == fx and sy == fy and t == 1:
# Special case:
# Each second, we must move one step
return False
# Optimal path's length = Chebyshev distance
chebyshev_dist = max( abs(sx-fx), abs(sy-fy) )
return chebyshev_dist <= t
複雜度分析
時間複雜度:
O(1) 使用Chebyshev distance估計，常數時間內可以計算出來。
空間複雜度:
O(1) 使用到的都是固定尺寸的臨時變數，為常數級別。
關鍵知識點
除了傳統的BFS + N8的路徑模擬演算法以外，其實，還可以使用Chebyshev distance來進行估計。
Chebyshev distance的定義就是兩個點座標，假設都沒有障礙物，在平面上N8 8連通走法的最短距離。
Chebyshev distance(x, y) = Max{ |x1-x2|, |y1-y2|}
從起點的視角來看，就像一個方形的同心紋路，一層一層，由內往外擴散。
Reference:
