力扣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;
        }
    };