题目链接
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
示例 1：
1
2
3
4
| 输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
|
示例 2：
1
2
3
| 输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
|
示例 3：
1
2
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
解释：上图所示路径不需要消耗任何体力。
|
二分+BFS~
我们可以二分最短距离，每一次从左上角往右下角 BFS 即可，注意 BFS 过程中的标记请尽量用数组完成，map 会非常耗时，AC代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
private:
int m, n, dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
public:
bool check(int x, vector<vector<int>> &heights) {
queue<pair<int, int>> q;
vector<int> vis(m * n);
pair<int, int> a, b;
q.push({0, 0});
vis[0] = 1;
while (!q.empty()) {
a = q.front();
q.pop();
if (a.first == m - 1 && a.second == n - 1) {
return 1;
}
for (int i = 0; i < 4; i++) {
b.first = a.first + dir[i][0];
b.second = a.second + dir[i][1];
if (b.first >= 0 && b.first < m && b.second >= 0 && b.second < n && !vis[b.first * n + b.second] &&
abs(heights[a.first][a.second] - heights[b.first][b.second]) <= x) {
vis[b.first * n + b.second] = 1;
q.push(b);
}
}
}
return 0;
}
int minimumEffortPath(vector<vector<int>> &heights) {
m = heights.size(), n = heights[0].size();
int l = 0, r = 1000000;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid, heights)) r = mid - 1;
else l = mid + 1;
}
return l;
}
};
|