-
Find all the paths from top-left to bottom-right and its efforts, pick the minimum one.
-
The “effort” of a path is the maximum absolute difference between two adjacent nodes in that path.
1x1, 1x2, 2x1, 2x2
A, B 1, 3
C, D 2, 7
dfs(A, 0)
dfs(B, 2)
dfs(D, 4) = 4 (min)
dfs(C, 1)
dfs(D, 5) = 5-
Run DFS or BFS starting from top-left, update the effort during traversal, stop until reaching the bottom-right, add the current effort to effort list.
-
Then find the minimum from effort list.
fun bruteForce(heights: Array<IntArray>): Int {
val m = heights.size
val n = heights[0].size
val allEfforts = mutableListOf<Int>()
val visited = Array(m) { BooleanArray(n) }
dfs(heights, 0, 0, visited, 0, allEfforts)
return allEfforts.min()
}
private fun dfs(heights: Array<IntArray>, row: Int, col: Int, visited: Array<BooleanArray>, currentEffort: Int, allEfforts: MutableList<Int>) {
val m = heights.size
val n = heights[0].size
if (row !in 0 until m || col !in 0 until n) return
if (visited[row][col]) return
if (row == m - 1 && col == n - 1) {
allEfforts.add(currentEffort)
return
}
visited[row][col] = true
for (d in directions) {
val newRow = row + d[0]
val newCol = col + d[1]
if (newRow !in 0 until m || newCol !in 0 until n) continue
if (visited[newRow][newCol]) continue
val newEffort = abs(heights[row][col] - heights[newRow][newCol])
dfs(heights, newRow, newCol, visited, maxOf(currentEffort, newEffort), allEfforts)
}
// Backtrack
visited[row][col] = false
}-
Time complexity: We are going to find all the possible paths so we need to backtrack at each position, and there are at most 3 adjacent nodes to visit next, the time complexity is
3^(m x n)O(m x n), this is wrong as we are exploring the possible paths from a single node, the time complexity isO(m x n)for a single path, it's not the total complexity.
Suppose we have exact two paths A and B, path A has all minimum efforts, path B has all maximum efforts, then exploring path B is a waste.
1a, 100
1b, 1c
1a -> 100 -> 1c: 99
1a -> 1b -> 1c: 0 (winner)-
What if we can always explore the minimum effort at each step, then see if we can reach the destination. If not, we explore the sub-optimal path after that.
- We prioritize to visit the path with minimum effort at each step.
→ Priority Queue + Dijkstra’s
Min-Max 為何是二分？
裡面的 Max: 在 1631 題中，我們看的是「Maximum Effort（路徑上的最大高度差）」。
在物理上，你可以把這個 Maximum 想像成你的「腿長限制」。
如果你選定了一條路徑，這條路徑的 Maximum Effort 是 K，意思就是：「只要你的腿長有 K，你就能無懼路徑上的任何起伏，順利走到終點。」
外面的 Mi:「為了順利走到終點，我的腿長『至少』要多長？」。
我們就從 1, 2, 3, ... 開始往上找，看看這樣能不能走到終點？可以發現，答案呈現
X, X, X, O, O, O的狀態，在超過某個數值之後就開始都可以通過 (單調性)，這就是一個典型的二分搜尋問題了。
Binary search is for finding a value in "sorted array", but there is no such sorted array in this problem, either the grid or paths is unsorted. The "sorted array" is hidden in the range of possible answer.
- Let's say the maximum absolute difference range from 0 to 100.
- The answer must be in that range
[0..100]. - This range
[0..100]is the sorted array that we can apply the binary search.
We use effort to represent the maximum absolute difference in heights between two consecutive cells of the route. (Aligned the problem description)
Let's take a look how do we apply binary search on answer in this problem:
- Search range: Given a minimum and maximum in the grid, the possible maximum effort =
abs(max - min), the possible minimum effort is0(same height). - Monotonicity: If there exists a path which effort is
k, then we can definitely find a path which effort isk + 1or largerk. (It's constraints)
We guess an effort k and check if there exists a path from source to destination that under that effort constraints. If we can reach the destination (via DFS or BFS), we try to find a smaller threshold. Otherwise, we try to find a larger threshold.
可以上下左右走，沒有無後效性，無法用動態規劃做。無腦搜索的話因為沒有什麼障礙或限制，效率非常差。可以二分猜答案;也可以貪心找 (Dijkstra's)，先找出所有的落差值，從最小的值開始串，看能不能串出從左上到右下的路徑。
fun minimumEffortPath(heights: Array<IntArray>): Int {
val m = heights.size
val n = heights[0].size
var left = 0 // Minimum effort is 0, not 1, the height difference can be 0. (same height)
var right = abs(heights.maxOf { it.max() } - heights.minOf { it.min() })
while (left <= right) {
val middle = left + (right - left) / 2
val canReach = dfs(heights, 0, 0, Array(m) { BooleanArray(n) }, middle)
if (canReach) {
right = middle - 1
} else {
left = middle + 1
}
}
return left
}
// We traverse the grid using DFS and check if we can reach the destination with the threshold.
private fun dfs(
heights: Array<IntArray>,
x: Int,
y: Int,
visited: Array<BooleanArray>,
threshold: Int
): Boolean {
val m = heights.size
val n = heights[0].size
if (x == m - 1 && y == n - 1) return true
visited[x][y] = true
var result = false
for (d in directions) {
val newX = x + d[0]
val newY = y + d[1]
if (newX !in 0 until m || newY !in 0 until n) continue
if (visited[newX][newY] == true) continue
val diff = abs(heights[x][y] - heights[newX][newY])
if (diff <= threshold) {
result = dfs(heights, newX, newY, visited, threshold) || result
}
}
return result
}- Time Complexity:
O(m * n * log(R))whereRis the maximum possible value range. - Space Complexity:
O(m * n).
Explore the path greedily, always choose the path with the minimum effort.
fun dijkstra(heights: Array<IntArray>): Int {
val m = heights.size
val n = heights[0].size
val efforts = Array(m) { IntArray(n) { Int.MAX_VALUE } }
val queue = PriorityQueue(compareBy<Cell> { it.effort })
queue.add(Cell(0, 0, 0))
efforts[0][0] = 0
while (queue.isNotEmpty()) {
val (row, col, effort) = queue.poll()
// Skip the stale
if (effort > efforts[row][col]) continue
// Reach the destination
if (row == m - 1 && col == n - 1) {
return effort
}
for (d in directions) {
val newRow = row + d[0]
val newCol = col + d[1]
if (newRow !in 0 until m || newCol !in 0 until n) continue
val nextEffort = abs(heights[newRow][newCol] - heights[row][col])
// Update the effort to accumulate the adjacent cell.
val newEffort = maxOf(effort, nextEffort)
if (newEffort < efforts[newRow][newCol]) {
queue.add(Cell(newRow, newCol, newEffort))
efforts[newRow][newCol] = newEffort
}
}
}
return -1
}