C++刷leetcode(最小体力消耗路径)【二分查找+深度优先搜索】

糖逗

题目描述：

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (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[x][y] = 1;
        for(int k = 0; k < 4; k++){
            int temp1 = x + direct[k][0];
            int temp2 = y + direct[k][1];//新增就要判断是否越界
            if(temp1 >= 0 && temp1 < len1 && temp2 >= 0 && temp2 < len2 && visit[temp1][temp2] == 0 && abs(input[x][y]-input[temp1][temp2]) <= 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[0].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;
    }
};

糖逗

不需要回溯吗

糖逗

不需要回溯，因为一次通路错了，该路径就走不通了