最短路徑應用: 遊戲模擬 Jump Game IV 青蛙過河 IV_Leetcode_#1345
題目敘述
題目會給我們一個輸入陣列arr，起始點固定在索引為0的位置，
終點固定在索引為n-1的位置。
假設當下所在的索引位置為i，那麼每次移動的時候，可以跳到i-1，i+1，或者其他和我有相同元素值的位置arr[j], where arr[j] = arr[i]。
例如:
假設當下在i=3的位置，arr[i] = 5，那麼下一步可以跳到i-1=2 或者i+1=4，或者陣列上其他陣列元素值=5的位置。
請問，從起點0出發跳到終點n-1，所需要的最小跳躍次數為多少?
測試範例
Example 1:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
arr[0] 跳到 arr[4]，因為兩者的元素值相同，都是100
arr[4] 跳到 arr[3]，3 = 4-1 是相差一隔的鄰居
arr[3] 跳到 arr[9]，因為兩者的元素值相同，都是404
Example 2:
Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.
起點剛好等於終點，不用跳就已經抵達終點。
所以0次。
Example 3:
Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.
arr[0] 可以直接跳到 arr[7]，因為兩者的元素值相同，都是7
約束條件
Constraints:
1 <= arr.length <= 5 * 10^4
陣列長度界於1~五萬之間。
-10^8 <= arr[i] <= 10^8
每個陣列元素值界於 負一億~正一億 之間。
演算法
題目已經無形中保證一定有解，為什麼?
因為最差情況下，就是每次都從i往右跳一格到i+1，總有一步會抵達終點n-1。
但是，題目要問的是從起點0到終點n-1的最短路徑需要幾次跳躍?
抽象的想，可以把arr[i]每個陣列格子都視為一個節點。
然後 arr[i] 和 arr[i-1], arr[i+1]各有一條邊相連，成本為1。
假如arr[j] = arr[i] 元素值相等，arr[i] 也和其他的arr[j] 有邊相連，成本為1。
到這裡，就把原本跳躍次數的問題，轉化成圖論中的最短路徑搜索問題，
起點為Node 0，終點為 n-1，最少要經過幾條邊(相當於幾次跳躍)才能抵達。
在無權重的圖 或者 權重都相等的圖中尋找最短路徑，那很自然就會想到BFS先天具有點播源擴散的特質，也因此具有最短路徑的搜索性質。
我們只要從Node 0 開始進行BFS廣度優先搜尋，一層一層往外拜訪，
當拜訪到Node n-1的時候，
當下的步數 = 最短路徑長度 = 從起點到終點的最小跳躍次數。
程式碼 BFS先天在無權圖 或者 等權圖 具有最短路徑的特質
class Solution:
def minJumps(self, arr):
n = len(arr)
destination = n-1
## Dictionary: a group of the same number
# key: number
# value: idx of number
same_number = defaultdict(list)
for idx, number in enumerate(arr):
same_number[number].append(idx)
# src = 0, step = 0
bfs_q = deque([(0, 0)])
# visited set
seen = set([0])
# Launch BFS from starting index = 0
# BFS naturaly has shortest path from source to destination.
while bfs_q:
cur, step = bfs_q.popleft()
# Reach destination
if cur == destination:
return step
# Go to the neighbor to previous index as well as next index
for next_idx in (cur+1, cur-1):
if 0 <= next_idx < n and next_idx not in seen:
bfs_q.append( (next_idx, step+1) )
seen.add( next_idx )
# Go to friend index who has the same number with me
for next_idx in same_number[ arr[cur] ]:
if next_idx not in seen:
bfs_q.append( (next_idx, step+1) )
seen.add( next_idx )
# Avoid repeated redundant traversal which would not yield better result
del same_number[ arr[cur] ]
return -1
複雜度分析 BFS先天在無權圖 或者 等權圖 具有最短路徑的特質
令n=輸入陣列nums的長度 = 圖中的節點總數
時間複雜度:
從start拜訪整張圖，每個節點至多訪問一次，每個節點至少有兩條向外的指向邊。
最後一定能找到最短路徑(因為最差情況就是每次都往右走，總有一步會走到終點)。
拜訪整張圖所需時間為O(n)。
空間複雜度:
從起點開始BFS逐層搜索，每一層拜訪彼此相差一步的節點，最大長度為O(n)。
關鍵知識點
在無權重的圖 或者 權重都相等的圖中尋找最短路徑，那很自然就會想到BFS先天具有點播源擴散的特質，也因此具有最短路徑的搜索性質。
我們只要從Node 0 開始進行BFS廣度優先搜尋，一層一層往外拜訪，
當拜訪到Node n-1的時候，
當下的步數 = 最短路徑長度 = 從起點到終點的最小跳躍次數。
在這邊也整理了一些常用的BFS、DFS圖論中的應用場景，提供讀者作為參考。
Reference:
[1] Jump Game IV_Python O(n) by BFS with natural shortest path itself [w/ Comment]
