SwimInRisingWater [source code]
public class SwimInRisingWater {
static
/******************************************************************************/
class Solution {
static int[][] increments = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int swimInWater(int[][] grid) {
int N = grid.length;
assert grid[0].length == N;
PriorityQueue<Integer> pq = new PriorityQueue<> (new Comparator<Integer> () {
@Override
public int compare (Integer a, Integer b) {
return grid[a / N][a % N]- grid[b / N][b % N];
}
});
Set<Integer> seen = new HashSet<> ();
seen.add (0);
pq.offer (0);
int res = grid[0][0];
while (!pq.isEmpty ()) {
int cur = pq.poll (), x = cur / N, y = cur % N;
res = Math.max (res, grid[x][y]);
if (x == N - 1 && y == N - 1)
return res;
seen.add (cur);
for (int[] incre : increments) {
int nx = x + incre[0], ny = y + incre[1], next = nx * N + ny;
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !seen.contains (next))
pq.offer (next);
}
}
assert false : "unreachable";
return -1;
}
}
/******************************************************************************/
public static void main(String[] args) {
SwimInRisingWater.Solution tester = new SwimInRisingWater.Solution();
int[][][] inputs = {
{{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}}, {{16}},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[][] grid = inputs[2 * i];
int ans = inputs[2 * i + 1][0][0];
System.out.println (Printer.separator ());
int output = tester.swimInWater (grid);
System.out.printf ("%s -> %s, expected:%d\n",
Matrix.printMatrix (grid), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
最后大概写了一个上面的DFS; 首先这个题目本身的思路并不复杂, 虽然介绍的很复杂, 但是实际上就是让你找一条从起点走到终点的path, 然后这条path的最大值要是最小的; 当然了, 题目意思明白了, 不代表题目本身的思路简单; 我这里的思路是, 我从grid的每一个位置出发, 然后看能不能从这个cell出发, 然后分别往起点和终点走, 同时规定不许走比自己大的path; 这个解法最后是TLE了; 注意, 我后来差点认为这个算法本身不正确: 因为你从[i, j]往起点的half-path是可能和往终点走的half path进行一个重叠的; 但是我后来想了一下, 也没人规定不能走回头路;
另外想过了用DP的思路来做, 因为我们最后关心的是从每一个cell走到起点的时候, 所需要踩过的最大的一个cell; 看起来这个应该是有一个DP structure的; 不过当时想了半天并没有想出来; 更准确的说, 是没有办法找到一个合理的DP填表顺序, 所以最后的dependency是没有办法利用; 站在一个点上, 感觉所有的邻居的结果都需要, 这个时候就是无法设计一个合理的填表顺序了;
把这个TLE的代码先保存下来; 说实话, 如果找不到DP结构, 我这个从每一个中间点出发的思路其实是比naive的DFS要慢的, 因为每一个点都要走一次自己的DFS;
class Solution {
static int[][] increments = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int swimInWater(int[][] grid) {
int R = grid.length, C = grid[0].length;
int res = Integer.MAX_VALUE;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (grid[i][j] < res && can_reach (grid, i, j, grid[i][j], new int[] {0, 0}) && can_reach (grid, i, j, grid[i][j], new int[] {R - 1, C - 1}))
res = grid[i][j];
}
return res;
}
boolean can_reach (int[][] grid, int i, int j, int val, int[] dest) {
boolean res = false;
if (grid[i][j] < 0)
return false;
if (i == dest[0] && j == dest[1])
return true;
grid[i][j] = -grid[i][j];
for (int[] incre : increments) {
int x = i + incre[0], y = j + incre[1];
if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && Math.abs (grid[x][y]) <= val)
res = res || can_reach (grid, x, y, val, dest);
}
grid[i][j] = -grid[i][j];
return res;
}
}
以前碰到过, 如果DFS超时的时候, 一个思路就是换成BFS, 一般BFS会比DFS要稍微快一点; 这里可以尝试一下;
尝试写了一个DP算法:
class Solution {
static int[][] increments = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int swimInWater(int[][] grid) {
int R = grid.length, C = grid[0].length;
int[][] min_to_start = new int[R][C], min_to_end = new int[R][C];
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (i == 0 && j == 0)
min_to_start[i][j] = grid[0][0];
else if (i == 0)
min_to_start[i][j] = max (grid[i][j], min_to_start[i][j - 1]);
else if (j == 0)
min_to_start[i][j] = max (grid[i][j], min_to_start[i - 1][j]);
else
min_to_start[i][j] = max (grid[i][j], Math.min (min_to_start[i - 1][j], min_to_start[i][j - 1]));
}
for (int i = R - 1; i >= 0; i--) for (int j = C - 1; j >= 0; j--) {
if (i == R - 1 && j == C - 1)
min_to_end[i][j] = grid[i][j];
else if (i == R - 1)
min_to_end[i][j] = max (grid[i][j], min_to_end[i][j + 1]);
else if (j == C - 1)
min_to_end[i][j] = max (grid[i][j], min_to_end[i + 1][j]);
else
min_to_end[i][j] = max (grid[i][j], Math.min (min_to_end[i + 1][j], min_to_end[i][j + 1]));
}
int res = Integer.MAX_VALUE, cur_min;
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) if ((cur_min = max (min_to_start[i][j], min_to_end[i][j])) < res)
res = cur_min;
return res;
}
int max (int... nums) {
int max = Integer.MIN_VALUE;
for (int i : nums) if (i > max)
max = i;
return max;
}
static class Point {
int x, y;
Point (int x, int y) {this.x = x; this.y = y;}
}
}
我首先证明了, 一个最优的path肯定没有cycle: 有cycle就只会让一个path的最大值增加一些增大的可能性, 没有必要. 然后写了这样一个算法, 规定每一个cell找起点的时候只能向左或者向上, 找终点的时候只能向下或者向右. 但是还是错的, 看题目给的这个例子就知道了. 实际上找终点的时候也有可能向左. 这样最后填表顺序还是无法决定; 比如你看14, 14无论是到起点还是终点的位置, 最后都是既有向左也有向右的, 所以我后来想过, 直接把grid给左右反转再做一次的做法, 实际上也是不行的;
想写一个naive的DFS但是实际上也写不出来;
模仿editorial1写的上面的代码, 速度是53ms (NA).
editorial
Approach #1: Heap [Accepted]
Intuition and Algorithm
Let's keep a priority queue of which square we can walk in next. We always walk in the smallest one that is 4-directionally adjacent to ones we've visited.
When we reach the target, the largest number we've visited so far is the answer.
这个设计非常的elegant; 我感觉是不是这个做法就是我们想要的一个这个问题的原型; 这个问题实际上就是转换为: find the path from start to end, whose max value is the smallest. 事实上, 用semiring的观点来理解, 这个跟DJ算法, 甚至A*算法是有共同之处的; DJ算法可以理解为每一个cell就是1, 所以最后找的edge最少, 就变成了sum of path最小的; 只不过我们这里要找的不是sum, 而是max而已, 这种观点按照NLP的时候学的semiring的观点, 应该是完全可以用一个很微妙的转化就能解决的;
只能说Google现在的题目真的是越来越刁钻了; DJ算法变形也开始考了;
class Solution {
public int swimInWater(int[][] grid) {
int N = grid.length;
Set<Integer> seen = new HashSet();
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((k1, k2) ->
grid[k1 / N][k1 % N] - grid[k2 / N][k2 % N]);
pq.offer(0);
int ans = 0;
int[] dr = new int[]{1, -1, 0, 0};
int[] dc = new int[]{0, 0, 1, -1};
while (!pq.isEmpty()) {
int k = pq.poll();
int r = k / N, c = k % N;
ans = Math.max(ans, grid[r][c]);
if (r == N-1 && c == N-1) return ans;
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)) {
pq.offer(ck);
seen.add(ck);
}
}
}
throw null;
}
}
复杂度是(N^2)lgN.
注意看他这里这个用一维坐标的技巧, 之前写数独那题的时候其实也是用过好几次了; 转换为一维坐标之后, iterate更加方便一些, 一个简单的+1就可以; 如果是二维坐标, 算起来可能稍微要麻烦一些;
顺便回忆一下cormen自己写的DJ算法:
void dijkstra(s) {
queue = new PriorityQueue<Vertex>();
for (each vertex v) {
v.dist = infinity; // can use Integer.MAX_VALUE or Double.POSITIVE_INFINITY
queue.enqueue(v);
v.pred = null;
}
s.dist = 0;
while (!queue.isEmpty()) {
u = queue.extractMin();
for (each vertex v adjacent to u)
relax(u, v);
}
}
void relax(u, v) {
if (u.dist + w(u,v) < v.dist) {
v.dist = u.dist + w(u,v);
v.pred = u;
}
}
刚开始我认为这个算法java不好实现, 因为java的PriorityQueue只有在get/put操作的时候才会维护order; 但是后来网上搜了一下: http://www.sanfoundry.com/java-program-mplement-dijkstras-algorithm-using-priority_queue/
好像也没什么难的; 因为每当你Poll了一次之后, 被调整dist的其实只有当前的被Poll出来的这个的neighbor. 不对, 我仔细看了一下上面那个算法, 那个算法实际的实现方式跟上面Cormen的代码稍微有点区别; Cormen的代码, 是一开始就全都enqueue进去; 而这个网站上面这个代码, 一开始只offer一个起点; 然后一次一个一个的来就跟BFS一样的处理顺序就基本没有什么困难了; 另外稍微提示一个回顾的细节, DJ算法是可以在一个pass里面把所有的node的distance都算出来的, 而不是针对某一个;
那么我还是想思考BFS, DJ, 和这里这个heap算法的共性.
突然发现, 好像其实DJ算法我也不会证明; 大概Google了一下, 好像就是一个inductive的证明, 每一步挑选的都是一个最短的reaching out edge, 然后用那个relax的不等式来证明每一步都是safe的; 都选择的是最好的, 没有犯错;
感觉这个题目其实并没有DJ算法复杂, 更多的其实是一个带weight的BFS; 如果用BFS来理解, 其实就简单很多; 因为BFS是不保存back pointer的, 更多的只是考虑一个reachability. 不对, 这个根本不是BFS, 别瞎鸡巴说; 只是写起来的代码结构相似而已, 实际的逻辑差别很大. 麻烦先在脑子里跑一点trace, 看看node们是怎么跟queue进行互动的, 差别完全很大;
这个算法假如有一条path, 是一个很小的path, 那么最后这个算法的behavior甚至很相似DFS, 其他的哪怕你是第一个level就被add进来的, 直接都不管你的; 只有当这条最promising的path碰到了一个大石头之后, 才重新考虑之前被遗忘的;
TODO: 从一个比较高的高度来总结这个算法到底怎么想到(path with min max value). 我一看到这个题目就觉得这个肯定是一个已经被解决的经典问题, 但是就是想不到好的说法; 到底这个算法跟DJ之间有哪些是共同的地方, 哪些是题目的个性导致的变动?
或许可以这样说, 找path, 所以用BFS的类似思路, BFS的核心是reachability, 反正path至少是要有这个的, 所以最后的算法肯定是在这个框架上面改; 然后因为要让整个path的最大值最小, 所以是一个greedy的问题, 我们就一直选择最小的值, 这样最后终于reach的时候, 得到的path肯定是通过尽可能选小的node来得到的;
感觉还是太牵强了; 当然, 这个题目如果你脑子里visual一个trace, 倒是很实在, 没有异议. 不过理论证明想不通; 难道非要和DJ一样用induction来证明?
Approach #2: Binary Search and DFS [Accepted]
Intuition and Algorithm
Whether the swim is possible is a monotone function with respect to time, so we can binary search this function for the correct time: the smallest T for which the swim is possible.
Say we guess that the correct time is T. To check whether it is possible, we perform a simple depth-first search where we can only walk in squares that are at most T.
这个算法很有意思啊, 搜搜题的另外一个思路; 实话说这个想法我稍微有一点; 不过我没有想到binary search. 一般的搜索问题, 怎么让你想到binary search? 当然, 有sorted这个就太明显了; 但是一般有连续值域的时候, 也是可以考虑binary search的场合;
另外, 看了下面的算法, 也可以看到为什么告诉你cell的上下限了, 给定了范围也是很提示binary search了; 当然, 如果你盯着permutation这一点看, 就容易被烟雾弹了; 他这里比较拉风的用了Stack来写DFS;
class Solution {
public int swimInWater(int[][] grid) {
int N = grid.length;
int lo = grid[0][0], hi = N * N;
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;
}
}
这个算法的复杂度也是(N^2)lgN;
另外他这里这个iterative的DFS看起来也是不复杂的; 你脑子里跑一下, 人家确实是DFS没问题的, 不过顺序比较乱, 是children order反过来的PreOrder; 好像awice就喜欢这样写DFS; 反正一般对order要求不严格的题目, 这个写法是完全足够的了, 而且因为写起来跟普通的BFS非常类似, 所以也好记;
@zestypanda said in C++ two solutions, Binary Search+DFS and Dijkstra+BFS, O(n^2logn), 11ms:
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.
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;
}
};
没想到这个算法居然更加快; 注意这里的binary search的写法: 因为我们要找的是较小的level, 所以当valid的时候, 是往左走而不是往右走;
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
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 -1;
}
};
Dijkstra with BFS optimization, O(n^2logn), 11 ms
Similar to above solution, but we can use BFS, which is more efficient, to expand reachable region.
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]);
queue<pair<int, int>> myq;
myq.push({cur[1], cur[2]});
while (!myq.empty()) {
auto p = myq.front();
myq.pop();
if (p.first == n-1 && p.second == n-1) return ans;
for (int i = 0; i < 4; ++i) {
int r = p.first + dir[i], c = p.second + dir[i+1];
if (r >= 0 && r < n && c >= 0 && c < n && visited[r][c] == 0) {
visited[r][c] = 1;
if (grid[r][c] <= ans)
myq.push({r, c});
else
pq.push({grid[r][c], r, c});
}
}
}
}
return -1;
}
};
脑子里面大概画了一下trace, 其实他这里第三种方法最后的效果跟第二种方法的实现是一样的, 都是尽可能的在reachable的范围里面挑选最小的一个, 一直走, 走到走不动了为止, 只不过第二种方法的这个挑选过程更加自动: 实际上第二种方法是可能探索超过一个promising的path的: 比如1,3,5,7和2,4,6,8这两条path, 轮流是min, 所以会轮流被探索; 但是这个明显是没有必要的; 第三种方法就是加了这个优化, 保证只有一条path彻底没有希望了, 再考虑其他的;
另外注意他这里的这个方向向量的存储方式;
事实上, 他第三个算法的写法思路非常简单, 找到一个最小的next neighbor, 然后直接BFS, 限制是不能超过这个neighbor自己的value; 如果能够找到最后的终点, 是最好, 如果不能, 抬走下一个; 这个思路简单到可怕, 但是自己相处来却并不简单, 比如, 我的一个担忧就是, 这样一个策略, 能保证找到终点吗? 这题来说, 实际上是可以找到的, 因为他加了一个操作, 假如当前的这个BFS被打断, 那么打断的这个node, 是被添加到了大的PriorityQueue里面的, 当备胎; 所以碰到uncertainty, 不要惊慌:
- enumerate
- 自己证明, 这个uncertainty不可能成立/发生, 不需要担心;
- 像这里一样, 一个额外的小操作, 就能保证无需担心这个uncertainty;
@tyuan73 said in [JAVA] DP + DFS:
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]);
}
}
刚开始没有看懂这个算法到底是什么思路, 后来脑子里画trace(就从[0,0]开始画), 然后大概理解了他的这个思路: 就是从起点开始, 然后向所有的方向同时走, 走到一个位置就更新当前的到这个位置的path的最低level, 然后将这个level带上继续向外扩散, 最后走到终点的时候, 就能找到the path with minimum level; 这个算法的点子虽然不错, 但是问题是这个算法的复杂度并不是特别好, 最坏情况:每一个cell都相等, 不对, 全部相等的在这里不是WorstCase; 不能光是想着这个是一个traversal.
思考这个traversal的方式: 这个算法是一个DFS的方式, 第一个DFS path, 肯定是可以走完全图的, 但是下一个起点的neighbor, 也有可能重新走完全图, override之前的结果(只要cell填的位置合理, 导致第一条path的level高于所有后面DFS path的cell对应的level就行了), 这样每一条DFS path都重新override全图, 最后的复杂度就是N^4了;
抛开这些, 算法本身的思路还是很明确的; 就是一个对DFS的直接变形; 我不认为他这个算法是一个DP, 他这个其实就是对每一个cell进行了一个annotate而已; 最起码, 这个算法没有明确的dependency顺序, 只是根据DFS的自然顺序进行override而已;
但是这个算法作为一个DFS的直接变形, 实际上按理来说比那个heap的做法要更容易想到的.
这个算法的弱点也就在于, 需要探索全图的结果, 所以最后的复杂度比如greedy的heap做法; 但是这个算法也有一个优势: 假如全图都是终点, 那么其实最后的复杂度和heap做法是一样的. heap做法只是对于单一终点的情况, 有格外好的prune表现;
@jwf said in 18ms Java Backtracking:
class Solution {
PriorityQueue<square> pq;
public int swimInWater(int[][] grid) {
pq = new PriorityQueue<>(new Comparator<square>() {
@Override
public int compare(square o1, square o2) {
return o1.value - o2.value;
}
});
int i=grid[0][0];
return Math.max(i,helper(grid, 0, 0, 0));
}
public int helper(int[][] grid, int i, int j, int max) {
if (i == grid.length - 1 && j == grid.length - 1) {
return max;
}
if (i - 1 >= 0 && grid[i - 1][j] != -1) {
pq.add(new square(i - 1, j, grid[i - 1][j]));
grid[i - 1][j] = -1;
}
if (j - 1 >= 0 && grid[i][j - 1] != -1) {
pq.add(new square(i, j - 1, grid[i][j - 1]));
grid[i][j - 1] = -1;
}
if (i + 1 < grid.length && grid[i + 1][j] != -1) {
pq.add(new square(i + 1, j, grid[i + 1][j]));
grid[i + 1][j] = -1;
}
if (j + 1 < grid.length && grid[i][j + 1] != -1) {
pq.add(new square(i, j + 1, grid[i][j + 1]));
grid[i][j + 1] = -1;
}
if (pq.isEmpty()) {
return max;
}
square temp = pq.poll();
if (temp.value <= max) {
return helper(grid, temp.i, temp.j, max);
} else {
return helper(grid, temp.i, temp.j, temp.value);
}
}
class square {
int i;
int j;
int value;
square(int ii, int jj, int v) {
i = ii;
j = jj;
value = v;
}
}
}
recursion写法的heap而已, 没有太大的惊喜;
@figurative said in O(n^2) Solution, Union-Find:
class Solution:
def swimInWater(self, grid):
def zhaobaba(x, y):
if baba[x][y] == (x, y):
return baba[x][y]
baba[x][y] = zhaobaba(baba[x][y][0], baba[x][y][1])
return baba[x][y]
def hebing(a, b):
a = zhaobaba(a[0], a[1])
b = zhaobaba(b[0], b[1])
if size[a[0]][a[1]] < size[b[0]][b[1]]:
baba[a[0]][a[1]] = b
size[b[0]][b[1]] += size[a[0]][a[1]]
else:
baba[b[0]][b[1]] = a
size[a[0]][a[1]] += size[b[0]][b[1]]
WEI = [[-1, 0], [0, -1], [1, 0], [0, 1]]
pos = {}
m = len(grid)
n = len(grid[0])
for i in range(m):
for j in range(n):
pos[grid[i][j]] = (i, j)
baba = []
size = []
for i in range(m):
new_list = []
for j in range(n):
new_list.append((i, j))
baba.append(new_list)
size.append([1] * n)
for i in range(m * n):
x, y = pos[i]
for wei in WEI:
tx = x + wei[0]
ty = y + wei[1]
if tx >= 0 and tx < m and ty >= 0 and ty < n:
if grid[tx][ty] <= i:
hebing((x, y), (tx, ty))
if zhaobaba(0, 0) == zhaobaba(m - 1, n - 1):
return i
看一个看不懂的算法的核心技巧, 是虚实交替: 不仅要笔算, 有时候也要积极的在脑子里抽象分析; 两者固守哪一个都不好. 如果上来就直接笔算, 因为对算法不熟悉, 所以笔算效率很低; 而没有笔算的危害我不说你也知道了, 很多算法光看代码是看不出来门道的. 一个比较好的flow就是, 虚分析开场, 先了解代码在干什么, 脑子里尽量形成记忆, 虽然你可能现在还不知道Why; 然后实分析, 进行笔算, 如果一轮笔算之后还是不理解, 那么重新虚分析, 交替进行;
这个算法写的还是非常的干练;
@figurative said in O(n^2) Solution, Union-Find:
@ngoc_lam
Sorry I forgot to add "link-by-size" optimization. I have updated the code.Note that my code also has "path compression", so the time complexity should be O(n^2*alpha(n^2)), where alpha is inverse Ackermann function, which is small and can be regarded as a constant. So it is fair to say the time complexity is O(n^2). You can refer to this slide https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf for details of proof.
反正我本身对UF算法也不熟悉, 所以这个算法我暂时只求看懂, 不知道怎么证明, 尤其是证明复杂度; UF算法的代码之前其实见到过一次, 这里重新复习一下;
另外, 注意他算法里面的各种细节, 比如用两个matrix来保存每一个cell对应的group的baba和size, 这个是一个可以学习的技巧, 毕竟数组模拟指针也不是第一次见到了; 一个值的注意的是他最后主函数里面合并的顺序, 是从最小的cell开始合并的(他成功的利用了permutation这个性质, 这样建立pos这个反向查询就很方便), 然后主见上升, 每一次合并结束都检查一下能够premature exit;
没有submission;
Problem Description
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:
- 2 <= N <= 50.
- grid[i][j] is a permutation of [0, ..., N*N - 1].
Difficulty:Hard
Total Accepted:834
Total Submissions:1.8K
Contributor:awice
Companies
google
Related Topics
binary searchheapdepth-first search
Hint 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.