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

// Binary search O(n^2 logn)
// class Solution {
// public:
//     int swimInWater(vector<vector<int>>& grid) {
//         int n = grid.size();
//         int low = grid[0][0], hi = n*n-1;
//         while (low < hi) {
//             int mid = low + (hi-low)/2;
//             if (valid(grid, mid)) 
//                hi = mid;
//             else
//                low = mid+1;
//         }
//         return low;
//     }
// private:
//     bool valid(vector<vector<int>>& grid, int waterHeight) {
//         int n = grid.size();
//         vector<vector<int>> visited(n, vector<int>(n, 0));
//         vector<int> dir({-1, 0, 1, 0, -1});
//         return dfs(grid, visited, dir, waterHeight, 0, 0, n);
//     }
//     bool dfs(vector<vector<int>>& grid, vector<vector<int>>& visited, vector<int>& dir, int waterHeight, int row, int col, int n) {
//         visited[row][col] = 1;
//         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] == 0 && grid[r][c] <= waterHeight) {
//                 if (r == n-1 && c == n-1) return true;
//                 if (dfs(grid, visited, dir, waterHeight, r, c, n)) return true;
//             }
//         }
//         return false;
//     }
// };


//O(n^2 logn)
class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size(), ans = max(grid[0][0], grid[n-1][n-1]);
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        vector<vector<int>> visited(n, vector<int>(n, 0));
        visited[0][0] = 1;
        vector<int> dir({-1, 0, 1, 0, -1});
        pq.push({ans, 0, 0});
        while (!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            ans = max(ans, cur[0]);
            for (int i = 0; i < 4; ++i) {
                int r = cur[1] + dir[i], c = cur[2] + dir[i+1];
                if (r >= 0 && r < n && c >= 0 && c < n && visited[r][c] == 0) {
                    if (r == n-1 && c == n-1) return ans;
                    pq.push({grid[r][c], r, c});
                    visited[r][c] = 1;
                }
            }
        }
        return 0;
    }
};

// Approach 2: PriorityQueue based shortest path search
// This is very similar to Dijkstra's algorithm except we don't maintain dist array and update dist for other vertices. We are just focused on finding the next closest vertex (the one that increases minimum time) and using it to reach towards target vertex.

// Reason why we can get by without dist array and update dist step is because of the way problem is defined, specifically because a vertex's dist value could become smaller than its grid value (if at all) only once i.e. at the time of exploring that vertex for the first time. After that, if we explore that vertex again through some other vertex, then time must be higher at that point and so the alternate path value (= time at that point) can not be better than what is already there. This is why we can get by without the "relax" step of Dijkstra's.


//We can use djikstra with dist as the difference of the levels. 
14924