# 1631. 最小体力消耗路径
## 题目描述
```
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
示例 1：
```
```
输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路劲差值最大值为 3 。
示例 2：
```
```
输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
示例 3：
```
```
输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。
提示：
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10e6
```
## 前置知识
* 二维矩阵
* [深度优先遍历](https://github.com/azl397985856/leetcode/blob/master/thinkings/DFS.md)
* [二分查找](/leetcode-solution/91/binary-search.md)
## 公司
* 暂无
## 思路
如果采用暴力解法， 需要找出所有的路径，然后返回最小代价的即可，时间复杂度是指数级别。回头看一下数据范围是 10e6，因此这种解法是不行的。
由于题目的解空间是 \[0, 10\*\*6 - 1]。
> 对解空间这个概念不熟悉的，可以看我之前的一篇题解[686. 重复叠加字符串匹配](/leetcode-solution/medium/686.repeated-string-match.md)
本质上，我们需要进行发问：
* 0 可以么？
* 1 可以么？
* 2 可以么？
* 。。。
直到找到第一个不可以的，我们返回前一个即可。
关于可不可以，我们可以使用 DFS 来做，由于只需要找到一条满足条件的，或者找到一个不满足的提前退出，因此最坏的情况是一直符合，并走到终点，这种情况下时间复杂度是 $(m \times n)$，因此总的时间复杂度是 $O(m \times n \times 10\*\*6)$。
实际上，上面的不断发问的过程不就是一个连续的递增序列么？ 我们的目标不就是在一个连续递增序列找指定值么？于是二分法就不难想到。
而且这道题本质就是二分查找中的**查找最右侧满足条件的值**，关于这个问题，我已经在 [【91 天学算法】二分查找](/leetcode-solution/91/binary-search.md) 中进行了详细描述，并给出了代码模板，直接套就可以了。
值得注意的是，我们只需要找到一个满足条件的路径即可，因此可以利用短路剪枝。
```py
return dfs(i + 1, j, heights[i][j], target) or dfs(i - 1, j, heights[i][j], target) or dfs(i, j + 1, heights[i][j], target) or dfs(i, j - 1, heights[i][j], target)
```
而不是写出下面的代码（下面的代码会超时）:
```py
top = dfs(i + 1, j, heights[i][j], target)
bottom = dfs(i - 1, j, heights[i][j], target)
right = dfs(i, j + 1, heights[i][j], target)
left = dfs(i, j - 1, heights[i][j], target)
return top or bottom or right or left
```
## 代码
代码支持：Python3
```py
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
lo, hi = 0, 10**6 - 1
m, n = len(heights), len(heights[0])
def dfs(i, j, pre, target):
if (i, j) in visited: return False
if i < 0 or i >= m or j < 0 or j >= n or abs(heights[i][j] - pre) > target: return False
if i == m - 1 and j == n - 1: return True
visited.add((i, j))
return dfs(i + 1, j, heights[i][j], target) or dfs(i - 1, j, heights[i][j], target) or dfs(i, j + 1, heights[i][j], target) or dfs(i, j - 1, heights[i][j], target)
# 查找最右侧满足条件的值
while lo <= hi:
visited = set()
mid = (lo + hi) >> 1
if dfs(0, 0, heights[0][0], mid): hi = mid - 1
else: lo = mid + 1
return lo
```
**复杂度分析**
m 为 矩阵的高度， n 为矩阵的长度。
* 时间复杂度：$O(4 \times m \times n \times log\_2 10^6)$，其中 $log\_2 10^6$ 为二分的次数， $4 \times m \times n$ 为每次 dfs 的时间。
* 空间复杂度：$O(m \times n)$，不管是递归的栈开销还是 visited 的开销都是 $O(m \times n)$。
## 相关问题
* [875. 爱吃香蕉的珂珂](/leetcode-solution/medium/875.koko-eating-bananas.md)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1631.path-with-minimum-effort.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.