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

<p>The rain starts to fall. At time <code>t</code>, the depth of the water everywhere is <code>t</code>. 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 <code>t</code>. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.</p>

<p>Return <em>the least time until you can reach the bottom right square </em><code>(n - 1, n - 1)</code><em> if you start at the top left square </em><code>(0, 0)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> grid = [[0,2],[1,3]]
<strong>Output:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg" style="width: 404px; height: 405px;" />
<pre>
<strong>Input:</strong> 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>Output:</strong> 16
<strong>Explanation:</strong> The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;&nbsp;n<sup>2</sup></code></li>
	<li>Each value <code>grid[i][j]</code> is <strong>unique</strong>.</li>
</ul>

#define rp(j, l, n) for(decltype(n) j = l; j < n; j++)
#define ll long long
#define pb push_back
#define us unsigned
#define vi vector<ll>
#define vvi vector<vi>
#define vpi vector<pair<ll, ll>>
#define vsi vector<set<ll>>
#define vb vector<bool>
#define pi pair<ll, ll>
#define si set<ll>
#define msi multiset<ll>
#define what_is(x) cerr << #x << " is " << x <<" ";
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;rp(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
#define inp(v, n) rp(i, 0, n)cin>>v[i];
#define out(v, n) rp(i, 0, n)cerr<<v[i]<<" "; cerr<<endl;
const ll INF = 1e18;
class Solution {
public:
    ll n;
    int swimInWater(vector<vector<int>>& grid) {
        n = grid.size();
        vector<vector<ll>> vals(n, vi(n, INF));
        vals[0][0] = grid[0][0];
        function<bool(pi, pi)> comp = [&](pi a, pi b)
        {
            return vals[a.first][a.second] > vals[b.first][b.second];
        };
        priority_queue<pi, vpi, function<bool(pi, pi)>> curr(comp);
        curr.push({0,0});
        while(!curr.empty())
        {
            pi p = curr.top();
            curr.pop();
            ll val = vals[p.first][p.second];
            for(auto ng : ngs(p))
            {
                if(vals[ng.first][ng.second] > max(val, (ll)grid[ng.first][ng.second]))
                {
                    vals[ng.first][ng.second] = max(val, (ll)grid[ng.first][ng.second]);
                    curr.push(ng);
                }
            }
        }
        return vals[n-1][n-1];
    }
    vector<pair<ll,ll>> ngs(pair<ll,ll> pos)
    {
        vector<pair<ll,ll>> ng;
        if(pos.first - 1 >= 0)ng.push_back({pos.first - 1, pos.second});
        if(pos.first + 1 < n)ng.push_back({pos.first + 1, pos.second});
        if(pos.second - 1 >= 0)ng.push_back({pos.first, pos.second -1});
        if(pos.second + 1 < n)ng.push_back({pos.first, pos.second + 1});
        return ng;
    }
};
20156