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

糖逗

题目描述：

1. 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
   
2. 
   
3. 一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
   
4. 
   
5. 请你返回从左上角走到右下角的最小 体力消耗值 。

复制代码

1. class Solution {
   
2. private:
   
3.     int len1, len2;
   
4.     vector<vector<int> >direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
   
5. public:
   
6.     //检查是否存在一条从(x,y)到终点的路径，该路径中相邻顶点绝对值差不大于max
   
7.     bool dfs(int x, int y, vector<vector<int> >&input, vector<vector<int> >& visit, int MAX){
   
8.         if(x == len1 - 1 && y == len2 - 1)return true;
   
9.         visit[x][y] = 1;
   
10.         for(int k = 0; k < 4; k++){
    
11.             int temp1 = x + direct[k][0];
    
12.             int temp2 = y + direct[k][1];//新增就要判断是否越界
    
13.             if(temp1 >= 0 && temp1 < len1 && temp2 >= 0 && temp2 < len2 && visit[temp1][temp2] == 0 && abs(input[x][y]-input[temp1][temp2]) <= MAX){
    
14.                 if(dfs(temp1, temp2, input, visit, MAX))return true;
    
15.             }
    
16.         }
    
17.         return false;
    
18.     }
    
19.     int minimumEffortPath(vector<vector<int>>& heights) {
    
20.         //二分查找法
    
21.         int res = 0;
    
22.         int left = 0, right = 1e6;
    
23.         len1 = heights.size(), len2 = heights[0].size();
    
24.         while(left < right){
    
25.             int mid = left + ((right - left) >> 1);//这样结算快一些，使用/计算超时
    
26.             vector<vector<int> > visit(len1, vector<int>(len2, 0));
    
27.             if(dfs(0, 0, heights, visit, mid) == true){
    
28.                 right = mid;
    
29.             }else{
    
30.                 left = mid + 1;
    
31.             }
    
32.         }
    
33.         return left;
    
34.     }
    
35. };

复制代码

糖逗

不需要回溯吗

糖逗

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