https://leetcode.com/problems/path-with-minimum-effort/description
1631. Path With Minimum Effort
給你一個陣列 heights[][],heights[i][j] 表示座標位置(i,j)的高度,兩個格子之間
的Effort被定義為兩個點的 heights 絕對值差,你可以往上下左右移動,求出從(0,0)
移動到最右下角的一個路徑,這個路徑途中的所有 Effort 都取最大,返回最小的路徑
Effort。
思路:
1.因為路徑可以往四個方向移動所以我們用BFS去處理確保可以獲得所有解。
2.先用一個 efforts[][] 紀錄到達這個格子的時候,該路徑的最小Effort,初始化
為一個很大的值,efforts[0][0] = 0。
3.把(0,0)推入 Queue 開始 BFS,往四個方向前進,下個點的 Effort 等於:
MAX(當前點和下個點的絕對值差, 當前點的Effort),如果下個點的Effort不能使
efforts[i][j] 變的更小就不更新,否則把下個點加入Queue繼續BFS。
Java Code: