778. Swim in Rising Water (Hard)

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

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

1. 2 <= N <= 50.
2. grid[i][j] is a permutation of [0, ..., N*N - 1].

Solutions

class Solution {
    public int swimInWater(int[][] grid) {
        int n = grid.length;

        boolean[][] visited = new boolean[n][n];

        // The key point is the use of PriorityQueue which sorts paths by max
        // time in ascending order
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        pq.offer(new int[]{0, 0, grid[0][0]});

        while (!pq.isEmpty()) {
            // Any possible paths will be compared and sorted, the popped one is the local optimal path
            int[] curr = pq.poll();

            int x = curr[0];
            int y = curr[1];
            int value = curr[2];

            // The optimal path is the first path reaches the destination which takes least time.
            if (x == n - 1 && y == n - 1) {
                return value;
            }

            // Ignore processed visited
            if (visited[x][y]) {
                continue;
            }

            // Attention Here !!!
            // Keep track of the visited cell.
            visited[x][y] = true;

            int[] R = new int[]{0, 0, -1, 1};
            int[] C = new int[]{-1, 1, 0, 0};

            // visit adjacent cells in four directions, not two. Just like waling through
            // a maze.
            for (int i = 0; i < 4; i++) {
                int nextX = x + R[i];
                int nextY = y + C[i];

                // ignore invalid cell location
                if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= n) {
                    continue;
                }

                if (visited[nextX][nextY]) {
                    continue;
                }

                // the least time cost will be the maximum between value and grid[nextX][nextY]
                int nextVal = Math.max(value, grid[nextX][nextY]);
                pq.offer(new int[]{nextX, nextY, nextVal});
            }
        }

        return -1;
    }
}

Incorrect Solutions

References