PacificAtlanticWaterFlow [source code]
public class PacificAtlanticWaterFlow {
static
/****************************************************************************/
class Solution {
static int[] moves = {-1, 0, 1, 0, -1};
boolean isInBound (int x, int y, int[][] mat) {
return x >= 0 && y >= 0 && x < mat.length && y < mat[0].length;
}
public List<int[]> pacificAtlantic (int[][] matrix) {
List<int[]> res = new ArrayList<> ();
if (matrix.length == 0 || matrix[0].length == 0)
return res;
int R = matrix.length, C = matrix[0].length;
boolean[][] pacific = new boolean[R][C], atlantic = new boolean[R][C];
Queue<int[]> pcells = new LinkedList<> (), qcells = new LinkedList<> ();
pcells.offer (new int[] {0, 0});
qcells.offer (new int[] {R - 1, C - 1});
for (int i = 0; i < R; i++) {
pacific[i][0] = true;
if (i != 0)
pcells.offer (new int[] {i, 0});
atlantic[i][C - 1] = true;
if (i != R - 1)
qcells.offer (new int[] {i, C - 1});
}
for (int j = 0; j < C; j++) {
pacific[0][j] = true;
if (j != 0)
pcells.offer (new int[] {0, j});
atlantic[R - 1][j] = true;
if (j != C - 1)
qcells.offer (new int[] {R - 1, j});
}
bfs (matrix, pcells, pacific);
bfs (matrix, qcells, atlantic);
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (pacific[i][j] && atlantic[i][j])
res.add (new int[] {i, j});
}
return res;
}
void bfs (int[][] mat, Queue<int[]> cells, boolean[][] reachable) {
int R = mat.length, C = mat[0].length;
while (!cells.isEmpty ()) {
int[] cur = cells.poll ();
int x = cur[0], y = cur[1];
for (int k = 0; k < 4; k++) {
int nex = x + moves[k], ney = y + moves[k + 1];
if (isInBound (nex, ney, mat) && !reachable[nex][ney] && mat[x][y] <= mat[nex][ney]) {
reachable[nex][ney] = true;
cells.offer (new int[] {nex, ney});
}
}
}
}
}
/****************************************************************************/
public static void main(String[] args) {
PacificAtlanticWaterFlow.Solution tester = new PacificAtlanticWaterFlow.Solution();
int[][][] inputs = {
{{1,2,3},{8,9,4},{7,6,5}}, {{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}},
{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}}, {{0,4},{1,3},{1,4},{2,2},{3,0},{3,1},{4,0}},
{{1,2,3,4},{12,13,14,5},{11,16,15,6},{10,9,8,7}}, {{0,3},{1,0},{1,1},{1,2},{1,3},{2,0},{2,1},{2,2},{2,3},{3,0},{3,1},{3,2},{3,3}},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[][] matrix = inputs[2 * i];
Set<Pair> ans = convertToPairs (new HashSet<> (Arrays.asList (inputs[2 * i + 1])));
Set<Pair> output = convertToPairs (new HashSet<> (tester.pacificAtlantic (matrix)));
boolean correct = output.equals (ans);
System.out.printf ("%s%s\n%s\n",
Matrix.printMatrix (matrix), Printer.wrap (output.toString (), correct ? 92 : 91), ans
);
if (!correct) {
Set<Pair> output_minus_ans = new HashSet<> (output);
output_minus_ans.removeAll (ans);
System.out.printf ("should not include\n%s\n", output_minus_ans);
Set<Pair> ans_minus_output = new HashSet<> (ans);
ans_minus_output.removeAll (output);
System.out.printf ("should include\n%s\n", ans_minus_output);
}
}
}
static class Pair {
int x, y;
Pair (int x, int y) {this.x = x; this.y = y; }
public String toString () {return String.format ("[%d, %d]", x, y); }
public boolean equals (Object obj) {
Pair that = (Pair) obj;
return that.x == this.x && this.y == that.y;
}
public int hashCode () {
int hash = 17;
hash = hash * 31 + ((Integer) this.x).hashCode ();
hash = hash * 31 + ((Integer) this.y).hashCode ();
return hash;
}
}
static Set<Pair> convertToPairs (Set<int[]> set) {
Set<Pair> res = new HashSet<> ();
for (int[] ar : set)
res.add (new Pair (ar[0], ar[1]));
return res;
}
static<T> Set<T> setDiff (Set<T> a, Set<T> b) { //<T> after access modifier
Set<T> res = new HashSet<> ();
for (T t : a) {
if (!b.contains (t)) {
res.add (t);
}
}
return res;
}
}
看起来像是一个要用DP来做的, 但是DP填表需要一个顺序, 这题明显是没有办法找到顺序的;
这个好像可以填表啊; 故意的啊, 故意让每一个ocean只touch两边; 所以就有一个方向了啊;
重新读题, 谁是从cell出来, 往外流的, 而不是从edge往cell里面灌;
养成一个习惯, 写代码的时候, 加TODO;
You must override hashCode() in every class that overrides equals(). Failure to do so will result in a violation of the general contract for Object.hashCode(), which will prevent your class from functioning properly in conjunction with all hash-based collections, including HashMap, HashSet, and Hashtable.
保证equal的两个东西, 要能hash到一起;
test的时候顺手联系一下这些基本操作; 这里hash的写法是仿照Sedgwick上面看到的;
然后就看到第一个test为什么被break了, 这题最后用DP还是不行的:
最后实际上比如你找Pacific的时候, 完全有可能不是只能向左向上走的; 这个问题好像之前有道题目碰到过类似的; 这个应该就是这道题的坑了;
那这题就没什么好办法了啊; 先把错误的DP代码保存下来:
...跟下面差不多, 省略了;
或许可以用DP来帮忙prune一下: DP这个做法说能的, 肯定是能, 但是说不能的, 肯定是不能; 所以如果说不能, 我们再去用穷搜去搜;
按照这样一个思路写下来; 记得最后DFS的时候还要加上memo(不仅要memo true, FALSE也要memo); 结果最后还是被TLE了;
看答案;
此时的错误代码, 虽然长, 其实比较简单:
class Solution {
static int[] moves = {-1, 0, 1, 0, -1};
public List<int[]> pacificAtlantic (int[][] matrix) {
List<int[]> res = new ArrayList<> ();
if (matrix.length == 0 || matrix[0].length == 0)
return res;
int R = matrix.length, C = matrix[0].length;
// DP search for pruning
boolean[][] reach_p = new boolean[R][C], reach_a = new boolean[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
reach_p[r][c] = r == 0 || c == 0 ||
(matrix[r][c] >= matrix[r - 1][c] && reach_p[r - 1][c]) ||
(matrix[r][c] >= matrix[r][c - 1] && reach_p[r][c - 1]);
}
}
List<int[]> failed = new ArrayList<> ();
for (int r = R - 1; r >= 0; r--) {
for (int c = C - 1; c >= 0; c--) {
reach_a[r][c] = r == R - 1 || c == C - 1 ||
(matrix[r][c] >= matrix[r + 1][c] && reach_a[r + 1][c]) ||
(matrix[r][c] >= matrix[r][c + 1] && reach_a[r][c + 1]);
if (reach_p[r][c] && reach_a[r][c])
res.add (new int[] {r, c});
else
failed.add (new int[] {r, c});
}
}
// DFS search for those failed on DP
for (int[] pair : failed) {
int x = pair[0], y = pair[1];
if (dfs (x, y, matrix, reach_p, new boolean[R][C]) && dfs (x, y, matrix, reach_a, new boolean[R][C]))
res.add (pair);
}
return res;
}
boolean dfs (int x, int y, int[][] mat, boolean[][] dp, boolean[][] visited) {
if (dp[x][y])
return true;
boolean res = false;
for (int i = 0; i < 4; i++) {
int next_x = moves[i] + x, next_y = moves[i + 1] + y;
if (isInBound (next_x, next_y, mat) && !visited[next_x][next_y] && mat[x][y] >= mat[next_x][next_y]) {
visited[next_x][next_y] = true;
if (dfs (next_x, next_y, mat, dp, visited)) {
res = true;
break;
}
visited[next_x][next_y] = false;
}
}
dp[x][y] = res;
return res;
}
boolean isInBound (int x, int y, int[][] mat) {
return x >= 0 && y >= 0 && x < mat.length && y < mat[0].length;
}
}
看完discuss最优解, 想要自己用UF来写一下; 这个时候要回顾一下UF的使用方法:
id is invisible
刚开始设计的时候的想法是, 直接让比如能够被reach的cell, 我全都给他ID是1; 这个看起来是很naive很直接的一个思路; 但是这个是完全没有理解UF的一个思路;
UF这个东西, 你作为他的client, 你是看不到每一个cell的ID的; 这个东西是他internal的东西; 你本身能看到的只有union和find这两个操作, 以及其他比如你自己定义的接口;
所以一开始, 所有cell的ID, 就应该是全部distinct的初始化, 然后你作为client允许的操作, 只有union和find, 这样来操作, 哪两个cell你想要union, 怎样; 至于union之后到底union到哪个ID下面去了, 根本不关你事; 相应的, 你自己直接给某个cell指定set ID, 这个就更加是错上加错了;
理解UF的一个比较好的例子就是之前OA做的Google开花的那道题目; 你client只能用union find这些, 直接与ID进行互动是绝对不允许的;
对应的, 比如想要用ID直接来表达, 是否reachable, 这个就更加错上加错了; 判断一个cell能够reachable的逻辑, 应该是你client自己在其他地方去实现的;
另外, 其实不要太害怕用UF这个思路, 理解了之后, 其实UF还是不难写的, 而且UF实际上debug也不困难; 就几个数组, 数值一打印就知道问题出在哪里了;
BFS/DFS direction
虽然这题最后我不准备用BFS和DFS来写; 但是我还是思考一下为什么我这题没有理解到水漫金山的思路; 这个思路其实以前也见到过;
我大概思考一下, 我认为一个可能的原因就是, 这题实际上sink是有很多的; 不对; 你换两个方向来思考:
- 如果是source去找sink; 你拿着一个source, 他找的sink其实你是不知道是哪一个; 虽然说sink其实是很多, 但是最后真正对你有用的就只有其中的某一个: 至于是哪一个你还不知道; 这个过程实际上类似Top-Down的recursion写法的DP;
- 如果是sink去找source: 其实sink我们是知道的, 就border这些; 每一个sink找的, 实际上是所有的source! 而不是说规定只找到一个source就结束了; 这样一个过程, 可以极大的加快效率, 有点类似DP的Bottom-Up的过程; 注意下面discussion最优解给的那个DFS, 实际上也是一个Bottom-Up的过程, 跟我自己写的DFS完全不一样;
另外这题的UF直接的思路肯定是用二维数组, 后来想了一下, 还是用一维数组好一点; 不然你二维数组比如parent里面entry存放的是一个数字, 你可以用1D的index来存... 不对, 好像也可以; 1D的好写一些; 不过我决定锻炼一下, 谢谢2D的UF, 反正还没有写过;
注意, 即使是用UF, 这个也是一个水漫金山的思路; 所以这个方向转换始终是这道题目的核心;
很遗憾, 最终宣告UF思路是失败的: 这个是失败的时候的代码;
class Solution {
static int[] moves = {-1, 0, 1, 0, -1};
boolean isInBound (int x, int y, int[][] mat) {
return x >= 0 && y >= 0 && x < mat.length && y < mat[0].length;
}
public List<int[]> pacificAtlantic (int[][] matrix) {
List<int[]> res = new ArrayList<> ();
if (matrix.length == 0 || matrix[0].length == 0)
return res;
int R = matrix.length, C = matrix[0].length;
UnionFind ufp = new UnionFind (matrix), ufa = new UnionFind (matrix);
// pre union all borders
for (int j = 0; j < C - 1; j++) {
ufp.union (0, j, 0, j + 1);
ufa.union (R - 1, j, R - 1, j + 1);
}
for (int i = 0; i < R - 1; i++) {
ufp.union (i, 0, i + 1, 0);
ufa.union (i, C - 1, i + 1, C - 1);
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) { // water unions land, rather than land unions water
for (int k = 0; k < 4; k++) {
int landx = i + moves[k], landy = j + moves[k + 1];
if (isInBound (landx, landy, matrix) && ufp.connected (0, 0, i, j) && matrix[i][j] <= matrix[landx][landy]) {
boolean success = ufp.union (i, j, landx, landy);
}
}
}
}
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
for (int k = 0; k < 4; k++) {
int landx = i + moves[k], landy = j + moves[k + 1];
if (isInBound (landx, landy, matrix) && ufa.connected (R - 1, C - 1, i, j) && matrix[i][j] <= matrix[landx][landy]) {
boolean success = ufa.union (i, j, landx, landy);
}
}
}
}
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (ufp.connected (0, 0, i, j) && ufa.connected (R - 1, C - 1, i, j))
res.add (new int[] {i, j});
}
return res;
}
class UnionFind {
int[][] parent; // 2D array so client interface is easier to use
int[][] rank;
int C;
UnionFind (int[][] mat) {
int R = mat.length;
this.C = mat[0].length;
parent = new int[R][C];
rank = new int[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) { // rank starts with 0, id starts with myself
parent[i][j] = i * C + j;
rank[i][j] = 0;
}
}
}
int find (int x, int y) {
if (parent[x][y] != x * C + y) // DONOT use WHILE here!!!
parent[x][y] = find (parent[x][y] / C, parent[x][y] % C);
return parent[x][y];
}
boolean union (int x1, int y1, int x2, int y2) { // add return value to indicate whether anything changed
int root1 = find (x1, y1), root2 = find (x2, y2);
int root1x = root1 / C, root1y = root2 % C, root2x = root2 / C, root2y = root2 % C;
boolean changed = false;
if (root1 != root2) { // conditional merge
changed = true;
int rank1 = rank[root1x][root1y], rank2 = rank[root2x][root2y];
if (rank1 >= rank2) {
if (rank1 == rank2)
rank[root1x][root1y]++;
parent[root2x][root2y] = root1;
} else {
parent[root1x][root1y] = root2;
}
}
return changed;
}
boolean connected (int x1, int y1, int x2, int y2) {
return find (x1, y1) == find (x2, y2);
}
public String toString () {
return Arrays.deepToString (parent).replace ("],", "],\n");
}
}
}
实际上是花了很多心思的了; 但是还是失败;
第一个发现的问题是, 因为我们是water, 所以要判断自己是water才能进行union操作, 这个在header里面能看到; 体现在这个例子;
看这里这个2, 如果你不判断2是water, 2直接就去union自己上面的3, 但是这个是不合理的, 2根本就没有water结果强行自己和3攀亲戚了;
同时, 加上这个优化之后, 不能指望通过i, j的自然移动来union, 因为这个相当于强调只有左上角和右下角两个源头进行扩散; 但是实际上我们border上面的所有的点都是符合条件的source; 所以又加了一个pre union操作: 先把border都union起来;
但是这样还是有问题, 被test3给break, 而且问题相当致命:
问题就出在这个9, 我们在Pacific蔓延的时候, 正常刚到9的时候, 9是没有办法被union的: 自己不是water, 而10和16都没有办法拯救他, 8也是这样; 但是等你走到7的时候, 7会把union拯救进去, 但是没有办法把union进去了! 刚开始的时候我特意让所有的cell的union都采用4个方向, 实际上就是为了解决他这里这个蛇形的问题, 结果还是没有办法解决这里两步长度的蛇形回头;
想要解决这个问题, 只有两个办法, 一来就是让7对整行都进行union, 但是这样复杂度最后会完全无法接受; 一来就是设计一个recursion的思路, 就类似加法进位一样, 999+1从个位一直网上蔓延; 但是你发现一个问题没有, 如果你设计一个recursion思路, 就怎么样了? 就跟DFS没有区别了啊?
所以这题最后实际上还是有需要进行一个BFS/DFS操作的;
虽然最后没有成果, 还是学了很多东西, 尤其是UF的写法进一步熟悉, 学习了:
- 2D的UF的写法: 为了让需要进行二维操作的client的使用更方便, UF本身的实现稍微繁琐一点;
- union函数加上一个boolean返回值(C风格)对于debug很有帮助;
最后还是照搬人家的BFS写法, 好歹是AC了; 不得不说这个人的代码写的已经是很完善了; 速度是40(14), 倒是很一般; 不过不是不能接受;
editorial
https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/90733/Java-BFS-and-DFS-from-Ocean
- Two Queue and add all the Pacific border to one queue; Atlantic border to another queue.
- Keep a visited matrix for each queue. In the end, add the cell visited by two queue to the result.
BFS: Water flood from ocean to the cell. Since water can only flow from high/equal cell to low cell, add the neighboor cell with height larger or equal to current cell to the queue and mark as visited.
大概意思就是一个从ocean反过来往陆地走的思路; 如果是这样的话, 感觉这题UF可以做啊;
public class Solution {
int[][]dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new LinkedList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int n = matrix.length, m = matrix[0].length;
//One visited map for each ocean
boolean[][] pacific = new boolean[n][m];
boolean[][] atlantic = new boolean[n][m];
Queue<int[]> pQueue = new LinkedList<>();
Queue<int[]> aQueue = new LinkedList<>();
for(int i=0; i<n; i++){ //Vertical border
pQueue.offer(new int[]{i, 0});
aQueue.offer(new int[]{i, m-1});
pacific[i][0] = true;
atlantic[i][m-1] = true;
}
for(int i=0; i<m; i++){ //Horizontal border
pQueue.offer(new int[]{0, i});
aQueue.offer(new int[]{n-1, i});
pacific[0][i] = true;
atlantic[n-1][i] = true;
}
bfs(matrix, pQueue, pacific);
bfs(matrix, aQueue, atlantic);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(pacific[i][j] && atlantic[i][j])
res.add(new int[]{i,j});
}
}
return res;
}
public void bfs(int[][]matrix, Queue<int[]> queue, boolean[][]visited){
int n = matrix.length, m = matrix[0].length;
while(!queue.isEmpty()){
int[] cur = queue.poll();
for(int[] d:dir){
int x = cur[0]+d[0];
int y = cur[1]+d[1];
if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]){
continue;
}
visited[x][y] = true;
queue.offer(new int[]{x, y});
}
}
}
}
这个代码简洁漂亮; 看起来也没有很特殊, 为什么他这个就能成功呢; 感觉跟这个方向有关系, 也就是从海洋反攻陆地这个思路; 这个就有点DP的感觉在里面; 但是又不是完全的DP; 最后能够加速的原因还是, 离海洋比较近的cell, 先有了结果; 然后离海洋比较远的, 就可以利用这些结果, 而不用一路走到岸边, 才知道结果;
这个题目对于复杂度虽然卡的紧, 但是卡的还算在点子上, 算是比较有意思的;
他这里也没有太追求slick: 两个ocean就用两套数据结构来维护, 先写一个working的结果出来再说;
BFS这个是一个multihead的版本, 也不难理解吧, 反正;
看他具体的写法, 这里:
if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]){
continue;
}
最后一个判断, 就是下一个位置, 比当前的位置矮的话, 就不去; 因为我们现在这个BFS, 我们扮演的是海洋; 所以他的逻辑就是, 只往高处去爬.
知道为什么这个了; 重新看了一下他的解释, 我们现在是water, 所以我们肯定不能往下走啊; 这个差点忘记了; 那这里其实就没有很难理解了;
说到BFS, 一个小细节当然就是什么时候mark; 他这里是enqueue的时候mark, 也是常规操作;
下面是DFS; 不看他的代码之前, 你问问自己, 你自己怎么写DFS? 你现在是海边一个sink, 你进去甩鞭子, 那么你要达到什么效果呢? 这题实际上BFS确实是更加intuitive一点的: 有那种DP的由近及远的感觉; DFS到底图啥?
DFS version:
public class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new LinkedList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int n = matrix.length, m = matrix[0].length;
boolean[][]pacific = new boolean[n][m];
boolean[][]atlantic = new boolean[n][m];
for(int i=0; i<n; i++){
dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);
}
for(int i=0; i<m; i++){
dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (pacific[i][j] && atlantic[i][j])
res.add(new int[] {i, j});
return res;
}
int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){
int n = matrix.length, m = matrix[0].length;
if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
return;
visited[x][y] = true;
for(int[]d:dir){
dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);
}
}
}
DFS函数里面这个visited感觉命名不太好, 用reachable这种好像好一点;
所以我其实还是没有改变观念; 我自己的做法的时候, 是从一个source, 寻找任何一个border, 但是这里这个DFS完成的实际上是一个flooding的操作; 你看他返回值都没有的, 所有操作就是标记visited这个矩阵;
然后走就行了; 哎, 其实也不是很难理解, 然后我居然还没看懂;
看完这个我反而想自己用UF来写一下;
UNFINISHED
Problem Description
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
- The order of returned grid coordinates does not matter.
- Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
Difficulty:Medium
Total Accepted:25.5K
Total Submissions:73.3K
Contributor:LeetCode
Companies
google
Related Topics
depth-first searchbreadth-first search