Google | Swim in Rising Water

link: https://leetcode.com/problems/swim-in-rising-water/

from collections import deque
class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        def rec(grid,val):
            q=deque()
            q.append((0,0))
            n=len(grid)
            vis=[[0]*n for i in range(n)]
            vis[0][0]=1
            while q:
                r,c=q.popleft()
                if r==n-1 and c==n-1:
                    return True
                for u,v in [[-1,0],[1,0],[0,1],[0,-1]]:
                    nr=r+u
                    nc=c+v
                    if nr>-1 and nr<n and nc>-1 and nc<n and vis[nr][nc]==0 and grid[nr][nc]<=val:
                        vis[nr][nc]=1
                        q.append((nr,nc))
            return False
        l=grid[0][0]
        h=len(grid)**2
        ans=-1
        while l<=h:
            mid=(l+h)//2
            if rec(grid,mid):
                ans=mid 
                h=mid-1
            else:
                l=mid+1
        return ans