https://leetcode.com/problems/swim-in-rising-water/
Use either Dijkstra's, or binary search for the best time T for which you can reach the end if you only step on squares at most T.
X. PriorityQueue + BFS, Dijkstra
https://zhuanlan.zhihu.com/p/33590149
https://leetcode.com/problems/swim-in-rising-water/discuss/113770/Easy-and-Concise-Solution-using-PriorityQueue-PythonC%2B%2B
这道题给了我们一个二维数组，可以看作一个水池，这里不同数字的高度可以看作台阶的高度，只有当水面升高到台阶的高度时，我们才能到达该台阶，起始点在左上角位置，问我们水面最低升到啥高度就可以到达右下角的位置。这是一道蛮有意思的题目。对于这种类似迷宫遍历的题，一般都是DFS或者BFS。而如果有极值问题存在的时候，一般都是优先考虑BFS的，但是这道题比较特别，有一个上升水面的设定，我们可以想象一下，比如洪水爆发了，大坝垮了，那么愤怒汹涌的水流冲了出来，地势低洼处就会被淹没，而地势高的地方，比如山峰啥的，就会绕道而过。这里也是一样，随着水面不断的上升，低于水平面的地方就可以到达，直到水流到了右下角的位置停止。因为水流要向周围低洼处蔓延，所以BFS仍是一个不错的选择，由于水是向低洼处蔓延的，而低洼处的位置又是不定的，所以我们希望每次取出最低位置进行遍历，那么使用最小堆就是一个很好的选择，这样高度低的就会被先处理。在每次取出高度最小的数字时，我们用此高度来更新结果res，如果当前位置已经是右下角了，则我们直接返回结果res，否则就遍历当前位置的周围位置，如果未越界且未被访问过，则标记已经访问过，并且加入队列
证明的话，就是当通过优先队列bfs到解的时候，所有小于当前解的路径都试过了。
one part of sub function
another part of binary search, which simply check if
Space Complexity: O(N^2)O(N2), the maximum size of the stack.
方法2中的possible函数跟方法1很像，只不过没有用优先级队列，把排序的O(logN) 时间转移到二分搜索的O(logN) 时间了。
本题题干中提到了一个非常重要的前提："You can swim infinite distance in zero time",同时也给了一个干扰条件，那就是示例2里面的说明，"We need to wait until time 16 so that (0, 0) and (4, 4) are connected."。那么，游泳的人是否需要先游到(1,4)这个点然后等待到time16呢？把问题简化一下，游泳者可以直接在(0,0)等待到time16，这样问题就变成了在什么时间点，游泳的人可以从起点游到终点。在某一特定时间点，矩阵中所有大于这个时间的元素认为是障碍，这样是不是就是一个迷宫问题了？至于怎么找到最小的时间点，首先可以确定，最大的时间是矩阵中值最大的元素，最小的时间是起点元素和终点元素的较大值。显然，用二分查找非常合适
其实这道题还可以使用二分搜索法来做，属于博主的总结帖中LeetCode Binary Search Summary 二分搜索法小结的第四类，用子函数当作判断关系。由于题目中给定了数字的范围，那么二分搜索法的左右边界就有了，然后我们计算一个中间值mid，调用子函数来看这个水面高度下能否到达右下角，如果不能的话，说明水面高度不够，则 left = mid+1，如果能到达的话，有可能水面高度过高了，则right = mid，最终会到达的临界点就是能到达右下角的最低水面高度。那么来看子函数怎么写，其实就是个迷宫遍历问题，我们可以使用BFS或者DFS，这里使用了stack辅助的迭代形式的DFS来遍历，当然我们也可以使用queue辅助的迭代形式的BFS来遍历，都一样，如果在mid的水面高度下，遍历到了右下角，则返回true，否则返回false
https://leetcode.com/problems/swim-in-rising-water/discuss/118204/Java-DFS-and-Union-Find
我们也可以使用DP+DFS来做，这里使用一个二维dp数组，其中 dp[i][j] 表示到达 (i, j) 位置所需要的最低水面高度，均初始化为整型数最大值，我们的递归函数函数需要知道当前的位置 (x, y)，还有当前的水高cur，同时传入grid数组和需要不停更新的dp数组，如果当前位置越界了，或者是当前水高和 grid[x][y] 中的较大值大于等于 dp[x][y] 了，直接跳过，因为此时的dp值更小，不需要被更新了。否则 dp[x][y] 更新为较大值，然后对周围四个位置调用递归函数继续更新dp数组，最终返回右下位置的dp值即可
https://leetcode.com/problems/swim-in-rising-water/discuss/113743/JAVA-DP-%2B-DFS
since each item in max can be updated at most N^2 times, the upper boundary of this solution is O(n^4).
X. http://reeestart.me/2018/04/22/LeetCode-778-Swim-in-Rising-Water/
Backtrack - Java (TLE)
就不停的backtrack去尝试向不同的路游到右下角所需要的时间. 这个需要的时间就是当前path中最大的数字. 因为如果时间不到那个数字, 是不可能通得过那个格子的
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 time0, 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 time3. When the depth of water is3, 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:
2 <= N <= 50.- grid[i][j] is a permutation of [0, ..., N*N - 1]
Use either Dijkstra's, or binary search for the best time T for which you can reach the end if you only step on squares at most T.
X. PriorityQueue + BFS, Dijkstra
https://zhuanlan.zhihu.com/p/33590149
因为我们在时间t，只能通过高度为小于等于t的位置。因此，想要最快到达终点，我们需要等到某个时间t0，使得有一条路径上，最高的高度为t0。所以这道题的本质是找到从左上角到右下角，所经过最大值最小的路径，所经过的最大值。
从左上角开始，我们开始计算到达每个点所经历的最大值最小的路径的最大值。这个思想相当于DP，只是和大部分grid的DP问题不同，各个子问题之间的依赖关系并不固定地依存于各个格子之间的几何关系。每个格子的子问题的答案，是它周边四个邻居的子问题答案的最小值，和它自己在grid中value更大的那个。所以我们需要找到的访问顺序，让我们可以总是先访问子问题答案较小的格子。换言之，我们访问的格子的子问题答案，也有着单调非递减性。我们维持一个未计算的格子的边界，下一个计算的格子，就是边界中（子问题答案）最小的那个格子。和前一题一样，边界被保存在一个priority_queue中
http://www.cnblogs.com/grandyang/p/9017300.htmlhttps://leetcode.com/problems/swim-in-rising-water/discuss/113770/Easy-and-Concise-Solution-using-PriorityQueue-PythonC%2B%2B
这道题给了我们一个二维数组，可以看作一个水池，这里不同数字的高度可以看作台阶的高度，只有当水面升高到台阶的高度时，我们才能到达该台阶，起始点在左上角位置，问我们水面最低升到啥高度就可以到达右下角的位置。这是一道蛮有意思的题目。对于这种类似迷宫遍历的题，一般都是DFS或者BFS。而如果有极值问题存在的时候，一般都是优先考虑BFS的，但是这道题比较特别，有一个上升水面的设定，我们可以想象一下，比如洪水爆发了，大坝垮了，那么愤怒汹涌的水流冲了出来，地势低洼处就会被淹没，而地势高的地方，比如山峰啥的，就会绕道而过。这里也是一样，随着水面不断的上升，低于水平面的地方就可以到达，直到水流到了右下角的位置停止。因为水流要向周围低洼处蔓延，所以BFS仍是一个不错的选择，由于水是向低洼处蔓延的，而低洼处的位置又是不定的，所以我们希望每次取出最低位置进行遍历，那么使用最小堆就是一个很好的选择，这样高度低的就会被先处理。在每次取出高度最小的数字时，我们用此高度来更新结果res，如果当前位置已经是右下角了，则我们直接返回结果res，否则就遍历当前位置的周围位置，如果未越界且未被访问过，则标记已经访问过，并且加入队列
证明的话，就是当通过优先队列bfs到解的时候，所有小于当前解的路径都试过了。
Dijkstra using Priority Queue, O(n^2logn), 20 ms;
In every step, find lowest water level to move forward, so using PQ rather than queue
In every step, find lowest water level to move forward, so using PQ rather than queue
public int swimInWater(int[][] grid) {
int n = grid.length;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
boolean[][] visited = new boolean[n][n];
int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
visited[0][0] = true;
pq.offer(new int[]{0, 0, grid[0][0]});
while(!pq.isEmpty()){
int[] info = pq.poll();
int i = info[0], j = info[1], max = info[2];
for(int[] dir : dirs){
int newI = dir[0] + i, newJ = dir[1] + j;
if(newI < 0 || newI >= n || newJ < 0 || newJ >= n) continue;
if(!visited[newI][newJ]){
visited[newI][newJ] = true;
int newmax = Math.max(max, grid[newI][newJ]);
if(newI == n - 1 && newJ == n - 1) return newmax;
pq.offer(new int[]{newI, newJ, newmax});
}
}
}
return 0;
}
http://reeestart.me/2018/04/22/LeetCode-778-Swim-in-Rising-Water/
X. Bi-Section
http://www.stokastik.in/leetcode-swim-in-rising-water/
The time complexity for the above code is O(N^2∗logN)
public int swimInWater(int[][] grid) {int n = grid.length;if (grid[n - 1][n - 1] == n * n - 1) return n * n - 1;final PriorityQueue<Node> minHeap = new PriorityQueue<>();minHeap.offer(new Node(grid[0][0], 0, 0));int time = grid[0][0];while (!minHeap.isEmpty()) {final Node curr = minHeap.poll();if (grid[curr.i][curr.j] == -1) continue;grid[curr.i][curr.j] = -1;time = Math.max(curr.val, time);if (curr.i == n - 1 && curr.j == n - 1) return time;if (curr.i - 1 >= 0) minHeap.offer(new Node(grid[curr.i - 1][curr.j], curr.i - 1, curr.j));if (curr.i + 1 < n) minHeap.offer(new Node(grid[curr.i + 1][curr.j], curr.i + 1, curr.j));if (curr.j - 1 >= 0) minHeap.offer(new Node(grid[curr.i][curr.j - 1], curr.i, curr.j - 1));if (curr.j + 1 < n) minHeap.offer(new Node(grid[curr.i][curr.j + 1], curr.i, curr.j + 1));}return time;}private class Node implements Comparable<Node> {int val;int i;int j;Node(int val, int i, int j) {this.val = val;this.i = i;this.j = j;}public int compareTo(final Node other) {return this.val - other.val;}}
X. Bi-Section
http://www.stokastik.in/leetcode-swim-in-rising-water/
The time complexity for the above code is O(N^2∗logN)
reachable(int T) with T givengrid[N-1][N-1] is reachable. int swimInWater(vector<vector<int>>& grid) {
int N = grid.size(), l = grid[0][0], r = N * N - 1, m;
while (l < r) {
m = (l + r) / 2;
if (reachable(m, grid, N)) r = m;
else l = m + 1;
}
return r;
}
int reachable(int T, vector<vector<int>>& grid, int N) {
queue<pair<int, int>> bfs;
vector<vector<int>> seen(N, vector<int>(N, 0));
static int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};
bfs.emplace(0, 0);
seen[0][0] = 1;
while (bfs.size()) {
int x = bfs.front().first, y = bfs.front().second;
bfs.pop();
if (grid[x][y] <= T) {
if (x == N - 1 && y == N - 1) return true;
for (auto& d : dir) {
int i = x + d[0], j = y + d[1];
if (i >= 0 && i < N && j >= 0 && j < N && !seen[i][j]) {
seen[i][j] = 1;
bfs.emplace(i, j);
}
}
}
}
return false;
}
“是否能游”是一个随时间变化的单调函数，我们可以对这个函数进行二分查找，寻找“能游”的最小
假设正确的时间是
Time Complexity: O(N^2 \log N)O(N2logN). Our depth-first search during a call to possible is O(N^2)O(N2), and we make up to O(\log N)O(logN) of them.T 。假设正确的时间是
T。为了检查是否能游，我们执行一个简单的深度优先搜索，检查在 T 时刻 是否能搜索到目标结点。Space Complexity: O(N^2)O(N2), the maximum size of the stack.
方法2中的possible函数跟方法1很像，只不过没有用优先级队列，把排序的O(logN) 时间转移到二分搜索的O(logN) 时间了。
public int swimInWater(int[][] grid) {
int N = grid.length;
int lo = grid[0][0], hi = N * N; // 根据题目最下行: grid[i][j]<=(N*N - 1)
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (!possible(mi, grid)) {
lo = mi + 1;
} else {
hi = mi;
}
}
return lo;
}
public boolean possible(int T, int[][] grid) {
int N = grid.length;
Set<Integer> seen = new HashSet();
seen.add(0);
int[] dr = new int[] { 1, -1, 0, 0 };
int[] dc = new int[] { 0, 0, 1, -1 };
Stack<Integer> stack = new Stack();
stack.add(0);
while (!stack.empty()) {
int k = stack.pop();
int r = k / N, c = k % N;
if (r == N - 1 && c == N - 1)
return true;
for (int i = 0; i < 4; ++i) {
int cr = r + dr[i], cc = c + dc[i];
int ck = cr * N + cc;
if (0 <= cr && cr < N && 0 <= cc && cc < N && !seen.contains(ck) && grid[cr][cc] <= T) {
stack.add(ck);
seen.add(ck);
}
}
}
return false;
}
https://www.cnblogs.com/seyjs/p/9370561.html本题题干中提到了一个非常重要的前提："You can swim infinite distance in zero time",同时也给了一个干扰条件，那就是示例2里面的说明，"We need to wait until time 16 so that (0, 0) and (4, 4) are connected."。那么，游泳的人是否需要先游到(1,4)这个点然后等待到time16呢？把问题简化一下，游泳者可以直接在(0,0)等待到time16，这样问题就变成了在什么时间点，游泳的人可以从起点游到终点。在某一特定时间点，矩阵中所有大于这个时间的元素认为是障碍，这样是不是就是一个迷宫问题了？至于怎么找到最小的时间点，首先可以确定，最大的时间是矩阵中值最大的元素，最小的时间是起点元素和终点元素的较大值。显然，用二分查找非常合适
其实这道题还可以使用二分搜索法来做，属于博主的总结帖中LeetCode Binary Search Summary 二分搜索法小结的第四类，用子函数当作判断关系。由于题目中给定了数字的范围，那么二分搜索法的左右边界就有了，然后我们计算一个中间值mid，调用子函数来看这个水面高度下能否到达右下角，如果不能的话，说明水面高度不够，则 left = mid+1，如果能到达的话，有可能水面高度过高了，则right = mid，最终会到达的临界点就是能到达右下角的最低水面高度。那么来看子函数怎么写，其实就是个迷宫遍历问题，我们可以使用BFS或者DFS，这里使用了stack辅助的迭代形式的DFS来遍历，当然我们也可以使用queue辅助的迭代形式的BFS来遍历，都一样，如果在mid的水面高度下，遍历到了右下角，则返回true，否则返回false
https://leetcode.com/problems/swim-in-rising-water/discuss/118204/Java-DFS-and-Union-Find
I split this question to 2 questions:
- one part of sub function
reachable(int T)withTgiven - another part of binary search, which simply check if
grid[N-1][N-1]is reachable.
private int[][] dirs = {{0,-1}, {0,1},{1,0},{-1,0}};
public int swimInWater4(int[][] grid) {
int N = grid.length;
int lo = 0;
int hi = N*N -1;
while (lo < hi)
{
int middle = (lo + hi) >>>1;
boolean[][] visited = new boolean[N][N];
if(hasPath(grid, 0, 0, middle, visited))
{
hi = middle;
}else {
lo = middle +1;
}
}
return lo;
}
private boolean hasPath(int[][] grid, int i, int j, int time, boolean[][] visited)
{
int N = grid.length;
if(i == N -1 && j == N -1)return true;
visited[i][j] = true;
for(int[] dir: dirs)
{
int newI = i + dir[0];
int newJ = j + dir[1];
if(newI >= 0 && newJ >=0 && newI < N && newJ < N && !visited[newI][newJ] && grid[i][j] <= time && grid[newI][newJ] <= time)
{
if(hasPath(grid, newI, newJ, time, visited))return true;
}
}
return false;
}
Binary Search + DFS, O(n^2logn), 14ms
Binary Search range [0, n*n-1] to find the minimum feasible water level. For each water level, verification using DFS or BFS is O(n^2). DFS is slightly faster in practice.
Binary Search range [0, n*n-1] to find the minimum feasible water level. For each water level, verification using DFS or BFS is O(n^2). DFS is slightly faster in practice.
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;
}
def canReach(self,time,matrix): tl = [0] * len(matrix[0]) visit = [] for i in matrix: visit.append(tl[:]) row = len(matrix) column = len(matrix[0]) queue = [(0,0)] visit[0][0] = 1 while len(queue) > 0: x,y = queue.pop(0) #print x,y if x == row-1 and y == column-1: return True if x - 1 >= 0 and matrix[x-1][y] <= time and visit[x-1][y] == 0: queue.append((x-1,y)) visit[x-1][y] = 1 if x + 1 < row and matrix[x+1][y] <= time and visit[x+1][y] == 0: queue.append((x+1,y)) visit[x+1][y] = 1 if y - 1 >= 0 and matrix[x][y-1] <= time and visit[x][y-1] == 0: queue.append((x,y-1)) visit[x][y-1] = 1 if y + 1 < column and matrix[x][y+1] <= time and visit[x][y+1] == 0: queue.append((x,y+1)) visit[x][y+1] = 1 return False
X. DFS
我们也可以使用DP+DFS来做，这里使用一个二维dp数组，其中 dp[i][j] 表示到达 (i, j) 位置所需要的最低水面高度，均初始化为整型数最大值，我们的递归函数函数需要知道当前的位置 (x, y)，还有当前的水高cur，同时传入grid数组和需要不停更新的dp数组，如果当前位置越界了，或者是当前水高和 grid[x][y] 中的较大值大于等于 dp[x][y] 了，直接跳过，因为此时的dp值更小，不需要被更新了。否则 dp[x][y] 更新为较大值，然后对周围四个位置调用递归函数继续更新dp数组，最终返回右下位置的dp值即可
https://leetcode.com/problems/swim-in-rising-water/discuss/113743/JAVA-DP-%2B-DFS
since each item in max can be updated at most N^2 times, the upper boundary of this solution is O(n^4).
final static int[][] steps = {{0,1},{0,-1}, {1,0},{-1,0}};
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] max = new int[n][n];
for(int[] line : max)
Arrays.fill(line, Integer.MAX_VALUE);
dfs(grid, max, 0, 0, grid[0][0]);
return max[n-1][n-1];
}
private void dfs(int[][] grid, int[][] max, int x, int y, int cur) {
int n = grid.length;
if (x < 0 || x >= n || y < 0 || y >= n || Math.max(cur, grid[x][y]) >= max[x][y])
return;
max[x][y] = Math.max(cur, grid[x][y]);
for(int[] s : steps) {
dfs(grid, max, x + s[0], y + s[1], max[x][y]);
}
}
BTW It is possible to optimize the DFS solution using a cache and get O(m*n) time complexity.
If during the DFS we reach a Point which is too high for us - don't skip it, put it into the map for the appropriate elevation. When
If during the DFS we reach a Point which is too high for us - don't skip it, put it into the map for the appropriate elevation. When
time is increased - we will check this map. class Point{
int x;
int y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
// Keep a list of reached points for each elevation
Map<Integer, List<Point>> map = new HashMap<>();
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int swimInWater(int[][] a) {
boolean[][] visited = new boolean[a.length][a[0].length];
// a[0][0] is initial time
map.put(a[0][0], Collections.singletonList(new Point(0, 0)));
return processElevation(a, visited, a[0][0]);
}
// process all reached Points with the current time (elevation)
private int processElevation(int[][] a, boolean[][] visited, int time) {
// tricky, we need to skip not existed elevations
if(!map.containsKey(time)) return processElevation(a, visited, ++time);
// get all reached Points for the current time (elevation)
for (Point p : map.get(time)) {
if(dfs(a, visited, p.x, p.y, time)) return time;
}
return processElevation(a, visited, ++time);
}
// Simple DFS. But do not skip neighbors which are higher than the current time. Add them to a Map and process them later.
private boolean dfs(int[][] a, boolean[][] visited, int x, int y, int time) {
if(x<0 || x==a.length || y<0 || y==a[0].length || visited[x][y]) return false;
if(x==a.length-1 && y==a[0].length-1) return true;
visited[x][y]=true;
// check all neighbors
for (int[] dir : dirs) {
int xx = x+dir[0];
int yy = y+dir[1];
if(xx<0 || yy<0 || xx==a.length || yy==a[0].length) continue;
// if the elevation of the neighbor higher than the current time - add this neighbor to the map
if(a[xx][yy]>time) {
if(!map.containsKey(a[xx][yy])) map.put(a[xx][yy], new ArrayList<>());
map.get(a[xx][yy]).add(new Point(xx, yy));
}else{
boolean res = dfs(a, visited, xx, yy, time);
if(res) return true;
}
}
return false;
}
Union Find的想法和第三种DFS类似, 归根结底我们是要找到一条从左上角能连通到右下角的path. 那么既然可以在每个时间t做一遍dfs看是否能连通, 也可以在每个时间t直接做union-find在看是否连通. 不是就t++, 直到左上角和右下角连通为止.
class UF {
int[] id;
public UF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
public int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
public boolean isConnected(int p, int q) {
return root(p)==root(q);
}
public void union(int p, int q) {
if (isConnected(p, q)) return;
id[root(p)] = root(q);
}
}
public int swimInWater(int[][] grid) {
int N = grid.length;
UF uf = new UF(N*N);
int time = 0;
while(!uf.isConnected(0, N*N-1)) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] > time) continue;
if (i < N-1 && grid[i+1][j]<=time) uf.union(i*N+j, i*N+j+N);
if (j < N-1 && grid[i][j+1]<=time) uf.union(i*N+j, i*N+j+1);
}
}
time++;
}
return time - 1;
}
public int swimInWater(int[][] grid) {
int n = grid.length;
int start = grid[n-1][n-1];
int end = n*n - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isValid(grid, mid)) {
end = mid;
} else {
start = mid;
}
}
if (isValid(grid, start)) return start;
return end;
}
private boolean isValid(int[][] grid, int t) {
int n = grid.length;
DisjointSet djs = new DisjointSet(n * n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] > t) continue;
if (i - 1 >= 0 && grid[i-1][j] <= t) {
djs.union(i * n + j, (i-1) * n + j);
}
if (j - 1 >= 0 && grid[i][j-1] <= t) {
djs.union(i * n + j, i * n + (j - 1));
}
}
}
return djs.find(0) == djs.find(n * n - 1);
}
private class DisjointSet {
int[] father;
int[] rank;
public DisjointSet(int capacity) {
father = new int[capacity];
rank = new int[capacity];
for (int i = 0; i < capacity; i++) father[i] = i;
}
public int find(int x) {
if (father[x] == x) return x;
return father[x] = find(father[x]);
}
public void union(int x, int y) {
int xr = find(x);
int yr = find(y);
if (xr == yr) return;
if (rank[xr] == rank[yr]) {
rank[yr]++;
} else if (rank[xr] > rank[yr]) {
int tmp = xr;
xr = yr;
yr = tmp;
}
father[xr] = yr;
}
}
binary search and union find
public int swimInWater(int[][] grid) {
int N = grid.length;
int lo = 0;
int hi = N*N -1;
int end = hi;
while (lo < hi)
{
int middle = (lo + hi) >>>1;
UnionFind unionFind = new UnionFind(N*N);
for (int i = 0; i < N; i++) {
boolean noUnion = true;
for (int j = 0; j < N; j++) {
if(grid[i][j] > middle)continue;
// right
if(j < N -1 && grid[i][j +1] <= middle)
{
noUnion = false;
unionFind.union(i*N + j, i*N + j +1);
}
// down
if(i < N -1 && grid[i +1][j] <= middle)
{
noUnion = false;
unionFind.union(i*N +j, (i+1)*N + j);
}
}
if(noUnion)break;
}
if(unionFind.isConnected(0, end))
{
hi = middle;
}else {
lo = middle +1;
}
}
return lo;
}
public class UnionFind {
private int count;
private int[] parents;
private int[] rank;
public UnionFind(int size)
{
this.count = size;
parents = new int[count];
for (int i = 0; i < size; i++) {
parents[i] = i;
}
rank = new int[count];
}
public int find(int i)
{
while (parents[i] != i)
{
parents[i] = parents[parents[i]];
i = parents[i];
}
return parents[i];
}
public boolean union(int p, int q)
{
int pp = find(p);
int pq = find(q);
if(pp == pq)return false;
if(rank[pp] < rank[pq])
{
parents[pp] = pq;
}else {
if(rank[pp] == rank[pq])
{
rank[pp]++;
}
parents[pq] = pp;
}
return true;
}
public boolean isConnected(int p, int q)
{
int pp = find(p);
int pq = find(q);
return pp == pq;
}
public int getCount()
{
return this.count;
}
}X. http://reeestart.me/2018/04/22/LeetCode-778-Swim-in-Rising-Water/
Backtrack - Java (TLE)
就不停的backtrack去尝试向不同的路游到右下角所需要的时间. 这个需要的时间就是当前path中最大的数字. 因为如果时间不到那个数字, 是不可能通得过那个格子的
public int swimInWater(int[][] grid) {int n = grid.length;if (grid[n - 1][n - 1] == n * n - 1) return n * n - 1;final int[] res = { n * n };dfs(0, 0, grid, grid[0][0], 0, res);return res[0];}private void dfs(final int i, final int j, final int[][] grid, final int time, final int[] res) {if (i == grid.length - 1 && j == grid.length - 1) {res[0] = Math.min(res[0], time);return;}if (grid[i][j] == -1) return;final int save = grid[i][j];grid[i][j] = -1;if (i - 1 >= 0) dfs(i - 1, j, grid, Math.max(time, grid[i - 1][j]), res);if (i + 1 < grid.length) dfs(i + 1, j, grid, Math.max(time, grid[i + 1][j]), res);if (j - 1 >= 0) dfs(i, j - 1, grid, Math.max(time, grid[i][j - 1]), res);if (j + 1 < grid.length) dfs(i, j + 1, grid, Math.max(time, grid[i][j + 1]), res);grid[i][j] = save;}
Solution #2 - DP
很显然上面的backtracking是超时了. 那么有个优化的点就在于, 因为我们backtrack的过程中就是去不断尝试从左上角到达每一个cell所需要的时间, 而这个时间就是当前path中最大的数字.
那么也就是说对于每个点v，从左上角肯定有不同的path能到达v, 不同的path肯定会有不同的最大数字. 举个栗子在题目描述的example中, 15那个点, 有上下左右4个方向能进入到15这个点:
- 要从上面的21进来, 那么你肯定得等到t=21的时候.
- 要从左边的14进来, 那么从左上角到达14且不经过15的办法只能先到22, 然后22->14->15. 所以你只能等到t=22的时候.
- 要从右边的16进来, 那么你得等到t=16的时候,
- 要从下面的19进来, 最优的办法是先到16, 然后16->20->19->15. 所以得等到t=20的时候.
进过这样的分析, 我们很显然能知道从左上角到达15这个点最优的方法是从右边的16这条路进来, 也就是最短的耗时是t=16.
但是由于backtrack只是在不停的尝试, 当我们从某个方向进入15这个点的时候, 我们并不知道之前是否有其他路已经进来过了, 我们更不知道是否之前的路是否比当前的更好, 如果是的话, 我们根本就没有必要处理当前的情况了.
因此, 与其不停的尝试, 适当剪枝就能将上面的backtrack的优化的很好. (Discussion里别人说这个解法是DP, 但个人觉得更像是剪枝.)
这个思路转化成为代码就是在上面backtrack的基础上加一个dp[i][j]表示当前从左上角到达cell(i,j)的最优解.
public int swimInWater(int[][] grid) {int n = grid.length;if (grid[n - 1][n - 1] == n * n - 1) return n * n - 1;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dp[i][j] = Integer.MAX_VALUE;}}dfs(0, 0, grid, grid[0][0], 0, dp);return dp[n - 1][n - 1];}private void dfs(final int i, final int j, final int[][] grid, final int time, final int[][] dp) {if (i < 0 || j < 0 || i >= grid.length || j >= grid.length) return;final int currTime = Math.max(time, grid[i][j]);// 已经有了另一条路径能用更短的时间到达(i, j)if (currTime >= dp[i][j]) return;dp[i][j] = currTime;dfs(i - 1, j, grid, currTime, dp);dfs(i + 1, j, grid, currTime, dp);dfs(i, j - 1, grid, currTime, dp);dfs(i, j + 1, grid, currTime, dp);}
Solution #3 - DFS
这个DFS解法的思路和上面两种方法并不是一个套路. 但是其实理解起来也比较无脑, 感觉一开始应该想到的是这个方法.
因为水位是随着时间t在增长, 那么最无脑的想法就是在每个时间t做一遍dfs, 直到能从左上角dfs到右下角为止. 不能的话就t++然后再重头做一遍dfs.
public int swimInWater(int[][] grid) {int n = grid.length;if (grid[n - 1][n - 1] == n * n - 1) return n * n - 1;Set<Integer> visited = new HashSet<>();int time = -1;do {time++;visited.clear();dfs(0, 0, grid, time, visited);} while (!visited.contains(toId(n - 1, n - 1, n)));return time;}private void dfs(final int i, final int j, final int[][] grid, final int time, final Set<Integer> visited) {if (i < 0 || j < 0 || i >= grid.length || j >= grid.length) return;if (grid[i][j] > time || visited.contains(toId(i, j, grid.length))) return;visited.add(toId(i, j, grid.length));dfs(i - 1, j, grid, time, visited);dfs(i + 1, j, grid, time, visited);dfs(i, j - 1, grid, time, visited);dfs(i, j + 1, grid, time, visited);}private int toId(final int i, final int j, final int n) {return i * n + j;}
