判斷是否能在時間限制內抵達終點 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^9
• 0 <= 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:

[1] Python O(1) by Chebyshev distance [+ Visualization] - Determine if a Cell Is Reachable at a Given Time - LeetCode