class Solution {
    int[][] dirs = new int[][]{
        {-1,0},
        {1,0},
        {0, 1},
        {0, -1}
    };
    public int swimInWater(int[][] grid) {
        boolean[][] v = new boolean[grid.length][grid[0].length];
        int res = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> (a[2] - b[2]));
        q.add(new int[]{0,0,grid[0][0]});
        while(!q.isEmpty()){
            int[] cur = q.poll();
            if(v[cur[0]][cur[1]])
                continue;
            res = Math.max(res, cur[2]);
            if(cur[0] == grid.length - 1 && cur[1] == grid[0].length - 1)
                break;
            v[cur[0]][cur[1]] = true;
            for(int[] d : dirs){
                int nr = d[0] + cur[0];
                int nc = d[1] + cur[1];
                if(0 <= nr && nr < grid.length && 0 <= nc && nc < grid[0].length && !v[nr][nc]){
                    q.add(new int[]{nr, nc,grid[nr][nc]});
                }
            }
        }
        return res;
    }
}