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

``````class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int res = 0, n = grid.size();
unordered_set<int> visited{0};
vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.first > b.first;};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > q(cmp);
q.push({grid[0][0], 0});
while (!q.empty()) {
int i = q.top().second / n, j = q.top().second % n; q.pop();
res = max(res, grid[i][j]);
if (i == n - 1 && j == n - 1) return res;
for (auto dir : dirs) {
int x = i + dir[0], y = j + dir[1];
if (x < 0 || x >= n || y < 0 || y >= n || visited.count(x * n + y)) continue;
visited.insert(x * n + y);
q.push({grid[x][y], x * n + y});
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
helper(grid, 0, 0, grid[0][0], dp);
return dp[n - 1][n - 1];
}
void helper(vector<vector<int>>& grid, int x, int y, int cur, vector<vector<int>>& dp) {
int n = grid.size();
if (x < 0 || x >= n || y < 0 || y >= n || max(cur, grid[x][y]) >= dp[x][y]) return;
dp[x][y] = max(cur, grid[x][y]);
for (auto dir : dirs) {
helper(grid, x + dir[0], y + dir[1], dp[x][y], dp);
}
}
};
``````

``````class Solution {
public:
int swimInWater(vector<vector<int>>& grid) {
int n = grid.size();
int left = grid[0][0], right = n * n;
while (left < right) {
int mid = left + (right - left) / 2;
if (!helper(grid, mid)) left = mid + 1;
else right = mid;
}
return left;
}
bool helper(vector<vector<int>>& grid, int mid) {
int n = grid.size();
unordered_set<int> visited{0};
vector<vector<int>> dirs{{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
stack<int> st{{0}};
while (!st.empty()) {
int i = st.top() / n, j = st.top() % n; st.pop();
if (i == n - 1 && j == n - 1) return true;
for (auto dir : dirs) {
int x = i + dir[0], y = j + dir[1];
if (x < 0 || x >= n || y < 0 || y >= n || visited.count(x * n + y) || grid[x][y] > mid) continue;
st.push(x * n + y);
visited.insert(x * n + y);
}
}
return false;
}
};
``````

https://leetcode.com/problems/swim-in-rising-water/solution/#

https://leetcode.com/problems/swim-in-rising-water/discuss/113743/JAVA-DP-+-DFS

https://leetcode.com/problems/swim-in-rising-water/discuss/113765/Easy-and-Concise-Solution-using-Binary-Search-PythonC++

https://leetcode.com/problems/swim-in-rising-water/discuss/113758/C++-two-solutions-Binary-Search+DFS-and-Dijkstra+BFS-O(n2logn)-11ms

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation