本文主要是介绍力扣1631.最小体力消耗路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣1631.最小体力消耗路径
-
二分答案
- 判断是否有一条边权小于mid的路径
- bfs判断路径
-
class Solution {int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};public:int minimumEffortPath(vector<vector<int>>& heights) {int m = heights.size();int n = heights[0].size();auto check = [&](int mid) -> bool{queue<pair<int,int>> q;q.emplace(0,0);vector<int> seen(m*n);seen[0] = 1;while(!q.empty()){auto [x,y] = q.front();q.pop();for(int i=0;i<4;i++){int a = x + dx[i];int b = y + dy[i];if(a>=0 && a<m && b>=0 && b<n && !seen[a*n + b] && abs(heights[x][y] - heights[a][b]) <= mid){q.emplace(a,b);seen[a*n+b] = 1;}}}if(seen[m*n-1]) return true;else return false;};int l = 0,r = 999999;while(l<r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}return r;}};
这篇关于力扣1631.最小体力消耗路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
