二分＋dfs 1631. 最小体力消耗路径

二分模板

1 int searchRange(vector<int>& nums, int target) {
2         int l=0,r=nums.size()-1;
3         while(l<r){
4             int mid=l+r>>1;
5             if(check(mid))r=mid;
6             else l=mid+1;
7         }
8     return l;
9 }

来个题：

看见一个ac代码，可以用1~126的二分去找那个差值（枚举差值呗）

 1 class Solution {
 2     int m, n;
 3     vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
 4 public:
 5     int minimumEffortPath(vector<vector<int>>& heights) {
 6         m = heights.size(), n = heights[0].size();
 7         int l = 0, r = 1e6, mid, ans = 0;
 8         while(l <= r)
 9         {
10             mid = l + ((r-l)>>1);
11             vector<vector<bool>> vis(m, vector<bool>(n,false));
12             if(dfs(heights, vis, 0, 0, mid))
13                 {
14                     r = mid-1;
15                 ans = mid;
16             }
17             else
18                 l = mid+1;
19         }
20         return ans;
21     }
22     bool dfs(vector<vector<int>>& heights, vector<vector<bool>>& vis, int x, int y, int d)
23     {
24         if(x == m-1 && y == n-1)
25             return true;
26         vis[x][y] = true;
27         int i, j, k;
28         for(k = 0; k < 4; k++)
29         {
30             i = x + dir[k][0];
31             j = y + dir[k][1];
32             if(i>=0 && i<m && j>=0 && j<n && !vis[i][j]
33                && abs(heights[x][y]-heights[i][j]) <= d)
34             {
35                 if(dfs(heights, vis, i, j, d))
36                     return true;
37             }
38         }
39         return false;
40     }
41 };