> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/778.-swim-in-rising-water.md).

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

```cpp
// BFS Dijkstra
int swimInWater(vector<vector<int>>& grid) { // time: (n^2 * log(n)); space: O(n^2)
    const vector<pair<int, int> > dirs({ {-1, 0}, {1, 0}, {0, -1}, {0, 1} });
    const int n = grid.size();
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;
    pq.emplace(grid[0][0], 0, 0);
    int res = 0;
    grid[0][0] = -1; // mark as visited
    while (!pq.empty()) {
        auto [elevation, i, j] = pq.top(); 
        pq.pop();
        res = max(res, elevation);
        if (i == n - 1 && j == n - 1) return res;
        for (const pair<int, int>& dir : dirs) {
            int new_i = i + dir.first, new_j = j + dir.second;
            if (new_i < 0 || new_i >= n || new_j < 0 || new_j >= n || grid[new_i][new_j] == -1) continue;
            pq.emplace(grid[new_i][new_j], new_i, new_j);
            grid[new_i][new_j] = -1; // mark as visited
        }
    }
    return -1;
}
```

```cpp
// Binary Search + DFS
bool dfs(const vector<vector<int>>& grid, vector<vector<bool> >& visited, const vector<int>& dir, int waterLevel, int row, int col) {
    const int n = grid.size();
    visited[row][col] = true;
    for (int i = 0; i < 4; ++i) {
        int r = row + dir[i], c = col + dir[i+1];
        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] > waterLevel) continue;
        if (r == n-1 && c == n-1) return true;
        if (dfs(grid, visited, dir, waterLevel, r, c)) return true;
    }
    return false;
}
bool valid(const vector<vector<int> >& grid, int waterLevel) {
    const int n = grid.size();
    vector<vector<bool> > visited(n, vector<bool>(n, false));
    vector<int> dir({-1, 0, 1, 0, -1});
    return dfs(grid, visited, dir, waterLevel, 0, 0);
}
int swimInWater(vector<vector<int>>& grid) { // time: O(n^2 * log(n)); space: O(n^2)
    const int n = grid.size();
    int low = grid[0][0], high = n * n - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (valid(grid, mid) ) high = mid;
        else low = mid+1;
    }
    return low;
}
```

```cpp
// Union-Find
int find(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = find(roots, roots[i]);
}
void uni(vector<int>& roots, int x, int y) {
    x = find(roots, x), y = find(roots, y);
    if (x != y) roots[y] = x;
}
int swimInWater(vector<vector<int>>& grid) { // time: (n^2 * log(n)); space: O(n^2)
    const vector<pair<int, int> > dirs({ {-1, 0}, {1, 0}, {0, -1}, {0, 1} });
    const int n = grid.size();
    vector<bool> visited(n * n, false);
    vector<int> roots(n * n);
    vector<pair<int, int> > ids(n * n);
    // Initialization of roots vector
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int k = i * n + j;
            roots[k] = k;
            ids[k] = {i, j};
        }
    }
    // sort in ascending order
    auto cmp = [&grid](const pair<int, int>& id1, const pair<int, int>& id2) {
        return grid[id1.first][id1.second] < grid[id2.first][id2.second];  
    };
    sort(ids.begin(), ids.end(), cmp);
    for (const pair<int, int>& id : ids) {
        int i = id.first, j = id.second, k = i * n + j;
        visited[k] = true;
        for (const pair<int, int>& dir : dirs) {
            int new_i = i + dir.first, new_j = j + dir.second, new_k = new_i * n + new_j;
            if (new_i < 0 || new_i >= n || new_j < 0 || new_j >= n || !visited[new_k]) continue;
            uni(roots, k, new_k);
            if (find(roots, 0) == find(roots, n * n - 1)) return grid[i][j];
        }
    }
    return -1;
}
```