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