# 778    Swim in Rising Water

## 778. [Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/description/)

## 1. Question

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].

## 2. Implementation

**(1) Heap**

```java
class Solution {
    public int swimInWater(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        PriorityQueue<CellInfo> minHeap = new PriorityQueue<>();
        minHeap.add(new CellInfo(0, 0, grid[0][0]));

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Set<Integer> visited = new HashSet<>();
        visited.add(0);

        int res = 0;
        int n = grid.length;

        while (!minHeap.isEmpty()) {
            CellInfo curCell = minHeap.remove();
            res = Math.max(res, curCell.height);

            int row = curCell.row, col = curCell.col;

            if (row == n - 1 && col == n - 1) {
                return res;
            }

            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];

                if (isValid(grid, nextRow, nextCol, visited)) {
                    minHeap.add(new CellInfo(nextRow, nextCol, grid[nextRow][nextCol]));
                    visited.add(nextRow * n + nextCol);
                }
            }
        }
        return -1;
    }

    public boolean isValid(int[][] grid, int row, int col, Set<Integer> visited) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && !visited.contains(row * grid[0].length + col);
    }

    class CellInfo implements Comparable<CellInfo> {
        int row;
        int col;
        int height;

        public CellInfo(int row, int col, int height) {
            this.row = row;
            this.col = col;
            this.height = height;
        }

        public int compareTo(CellInfo that) {
            return this.height - that.height;
        }
    }
}
```

**(2) Binary Search**

```
```

## 3. Time & Space Complexity

**Heap:** 时间复杂度O(mn \* log(mn)), 空间复杂度O(mn)