# 778 Swim in Rising Water

Idea use pq to sort elements in increasing order of value whenver visiting an element, put all four neighbors to pq. pop out the top element and update t.

Pseudocode

visited
directions
pq<List:value, x, y>
initialize t: t = max(top-left, bottom-right)
push <t, 0, 0> to pq
while(pq is not empty)
    list = pq.pop
    update t by list[0]
    if(current element is at bottom-right)  return t
    check current element's neighbors(check boundary and visited or not)
        push to pq, mark visited as true

return -1

Code

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        int[][] dir = {{1, 0}, {-1, 0}, {0,1}, {0,-1}};
        PriorityQueue<Element> pq = new PriorityQueue<Element>(n*n, new Comparator<Element>(){
            @Override
            public int compare(Element p, Element q){
                return p.val < q.val ? -1: 1;
            }
        });

        int t = Math.max(grid[0][0], grid[n-1][n-1]);
        pq.add(new Element(t, 0, 0));

        while(!pq.isEmpty()){
            Element e = pq.poll();
            t = Math.max(t, e.val);
            if(e.x == n-1 && e.y == n-1)    return t;
            for(int i=0; i<4; i++){
                int x = e.x + dir[i][0];
                int y = e.y + dir[i][1];

                if(x >= 0 && x < n && y >= 0 && y < n && !visited[x][y]){
                    pq.add(new Element(grid[x][y], x, y));
                    visited[x][y] = true;
                }
            }
        }

        return -1;
    }

    private class Element{
        int val;
        int x;
        int y;
        public Element(int v, int xx, int yy){
            val = v;
            x = xx;
            y = yy;
        }
    }
}