778. Swim in Rising Water

Link

Solution

PriotiyQueue

由(0,0)開始進行4個方向進行traverse，並用priotiyQueue紀錄所visit的grid的elevation，然後由低海拔開始優先進行traverse開發到高的海拔並紀錄max值。 當到達(N-1, N-1)時就可以知道到達該點所遇到的最高海拔是多少。

因為透過priotiyQueue優先由低海拔的開始。所以第一次到達(N-1,N-1)一定是最小的case。

  public int swimInWater(int[][] grid) {
        int N = grid.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)-> a[2]-b[2]);
        boolean[][] isVisited = new boolean[N][N];
        int maxElevation = 0;
        pq.add(new int[]{0, 0, grid[0][0]});
        isVisited[0][0] = true;
        int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        while(!pq.isEmpty()){
            int[] point = pq.poll();
            maxElevation = Math.max(maxElevation, point[2]);
            
            isVisited[point[0]][point[1]] = true;
            for(int[] dir : dirs){
                int newI = point[0] + dir[0];
                int newJ = point[1] + dir[1];
                
                if(newI >= 0 && newI < N && newJ >= 0 && newJ < N && !isVisited[newI][newJ]){
                    if(newI == N-1 && newJ == N-1){
                        return Math.max(maxElevation, grid[newI][newJ]);
                    }
                    pq.offer(new int[]{newI, newJ, grid[newI][newJ]});
                }
            }
            
        }
        return 0;
        
    }