# 778. Swim in Rising Water

## Problem Statement

<br>

You are given an `n x n` integer matrix `grid` where each value `grid[i][j]` represents the elevation at that point `(i, j)`.

The 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 distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.

Return *the least time until you can reach the bottom right square* `(n - 1, n - 1)` *if you start at the top left square* `(0, 0)`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg)

<pre><code><strong>Input: grid = [[0,2],[1,3]]
</strong><strong>Output: 3
</strong>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.
</code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg)

<pre><code><strong>Input: grid = [[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]]
</strong><strong>Output: 16
</strong><strong>Explanation: The final route is shown.
</strong>We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
</code></pre>

&#x20;

**Constraints:**

* `n == grid.length`
* `n == grid[i].length`
* `1 <= n <= 50`
* `0 <= grid[i][j] < n2`
* Each value `grid[i][j]` is **unique**.

## Intuition

```
Approach:

We Try to traverse all paths and maintain , 
Prioirity Queue like Dikjstra type

{max_distance(peak), {row,col}} info

Max peak will be the peak observed till now
then if we hot condition n-1, n-1 we stop as min heap will give us min at top

Mainatin visited to avoid multiple visits

```

### Links

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

### Video Links

<https://www.youtube.com/watch?v=amvrKlMLuGY&ab_channel=NeetCode>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
typedef pair<int, pair<int,int>> pii;

class Solution {
public:
    bool check_val(int x, int y, int n){
        return x>=0 and y>=0 and x<n and y<n;
    }

    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<bool>> visited(n, vector<bool>(n,false));
        priority_queue< pii, vector<pii>, greater<pii> > pq;
        pq.push({grid[0][0], {0,0}});
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};

        while(!pq.empty()){
            int peak = pq.top().first;
            int row = pq.top().second.first, col = pq.top().second.second;
            pq.pop();

            if(row == n-1 and col == n-1)
                return peak;

            for(int i=0; i<4; i++){
                int nrow = row + dx[i];
                int ncol = col + dy[i];

                if(check_val(nrow, ncol, n) and !visited[nrow][ncol]){
                    int updated_peak = max(grid[nrow][ncol], peak);
                    pq.push({updated_peak, {nrow, ncol}});
                    visited[nrow][ncol] = true;
                }
            }
        }

        return -1;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###