力扣778.水位上升的泳池中游泳

力扣778.水位上升的泳池中游泳

• 二分 + bfs

•   class Solution {
        int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
    public:
        int swimInWater(vector<vector<int>>& grid) {
            int n = grid.size();
            auto check = [&](int mid) -> bool
            {
                queue<pair<int,int>> q;
                vector<int> st(n*n);
                q.emplace(0,0);
                st[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 < n && b < n && b >= 0 && !st[a*n+b] && grid[a][b] <= mid)
                        {
                            q.emplace(a,b);
                            st[a*n+b] = 1;
                        }
                    }
                }
                if(st[n*n-1]) return true;
                else return false;
            };
    
            int l = grid[0][0] , r = 2501;
            while(l<r) 
            {
                int mid = l + r >> 1;
                if(check(mid)) r = mid;
                else l = mid + 1;
            }
            return l;
        }
    };
  

原文地址：https://blog.csdn.net/Pisasama/article/details/140637639

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！