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: