C++刷leetcode(最小体力消耗路径)【二分查找+深度优先搜索】
本帖最后由 糖逗 于 2020-11-4 16:57 编辑题目描述：
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
class Solution {
private:
int len1, len2;
vector<vector<int> >direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
//检查是否存在一条从(x,y)到终点的路径，该路径中相邻顶点绝对值差不大于max
bool dfs(int x, int y, vector<vector<int> >&input, vector<vector<int> >& visit, int MAX){
if(x == len1 - 1 && y == len2 - 1)return true;
visit = 1;
for(int k = 0; k < 4; k++){
int temp1 = x + direct;
int temp2 = y + direct;//新增就要判断是否越界
if(temp1 >= 0 && temp1 < len1 && temp2 >= 0 && temp2 < len2 && visit == 0 && abs(input-input) <= MAX){
if(dfs(temp1, temp2, input, visit, MAX))return true;
}
}
return false;
}
int minimumEffortPath(vector<vector<int>>& heights) {
//二分查找法
int res = 0;
int left = 0, right = 1e6;
len1 = heights.size(), len2 = heights.size();
while(left < right){
int mid = left + ((right - left) >> 1);//这样结算快一些，使用/计算超时
vector<vector<int> > visit(len1, vector<int>(len2, 0));
if(dfs(0, 0, heights, visit, mid) == true){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
}; 不需要回溯吗{:10_272:} 不需要回溯，因为一次通路错了，该路径就走不通了{:10_327:}
页:
[1]