请问：[417] 太平洋大西洋水流问题 - 从高往低出流如何求解
来源：8-6 二维平面上的回溯法 Word Search
Potter520
2022-08-17
我看了一下题解，基本都是从边界往高处流，确实简单很多。
但是我做题的时候，思路就是陷入从高往低处流的解法上。
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function (heights) {
let ret = [];
let n = heights.length;
let meno = Array(n).fill(-1).map(() => Array(n).fill(-1));
let visited = Array(n).fill(false).map(() => Array(n).fill(false));
//! 疑问2：会死循环，因为从高往低流，相同值又会返回来遍历导致死循环，请问如何解决？
function dfsLT(heights, x, y) {
let left = top = true;
//left
for (let i = y; i >= 1; i--) {
if (heights[x][i - 1] > heights[x][i]) {
left = false;
break;
} else if (heights[x][i - 1] === heights[x][i]) {
left = dfs(heights, x, i - 1);
if (!left) {
break;
}
}
}
//top
for (let i = x; i >= 1; i--) {
if (heights[i - 1][y] > heights[i][y]) {
top = false;
break;
} else if (heights[i - 1][y] === heights[i][y]) {
top = dfs(heights, i - 1, y);
if (!top) {
break;
}
}
}
return left || top;
}
function dfsRB(heights, x, y) {
let right = bottom = true;
//right
for (let i = y; i < n - 1; i++) {
if (heights[x][i + 1] > heights[x][i]) {
right = false;
break;
} else if (heights[x][i + 1] === heights[x][i]) {
right = dfs(heights, x, i + 1);
if (!right) {
break;
}
}
}
//bottom
for (let i = x; i < n - 1; i++) {
if (heights[i + 1][y] > heights[i][y]) {
bottom = false;
break;
} else if (heights[i + 1][y] === heights[i][y]) {
bottom = dfs(heights, i + 1, y);
if (!bottom) {
break;
}
}
}
return right || bottom;
}
/* 判断此位置：是否可以流向左上&右下 */
function dfs(heights, x, y) {
if (meno[x][y] !== -1) {
return meno[x][y];
}
//! 疑问1: visited 已访问过，不管返回ture or false 都是不对的，因为无法确认此位置是否可以往下流。请问如何解决？
if (visited[x][y]) {
return false;
}
visited[x][y] = true;
let lt = rb = true;
do {
lt = dfsLT(heights, x, y);
if (!lt) {
break;
}
rb = dfsRB(heights, x, y);
} while (false);
meno[x][y] = lt && rb;
visited[x][y] = false;
return ret;
}
for (let x = 0; x < n; x++) {
for (let y = 0; y < n; y++) {
let res = dfs(heights, x, y);
if (res) {
ret.push([x, y]);
}
}
}
return ret;
};
代码中的2个疑问，麻烦老师解答一下。
如果我的思路错了，麻烦老师提供一个正向解题的思路，谢谢。
1回答
-
liuyubobobo
2022-08-20
我没有仔细推敲你的代码，我大概浏览了一下，认为理解了你的代码和你的问题，如果我下面的回答你认为是因为方向上没有完全理解你的代码的意思，可以再和我交流。
==========
你的问题 1 很好解决。visited 应该是 int。因为两种状态是不够描述的，此时我们需要三种状态。我一般习惯于：-1 表示没有访问过；0 表示访问过但是无法到达；1 表示访问过但是可以到达。
当然，如果你一定要使用 bool，也是可以的。但此时需要两个 bool 矩阵。visited[i][j] 表示 i, j 是否访问过；ok[i][j] 表示 i,j 能否到达。当 visited[i][j] 为 false 的时候，ok[i][j] 没有意义（也不应该被访问）。
（在我下面给出的实现中，将使用 int = -1, 0, 1 的定义。）
==========
你的问题 2 是这个问题无法“简单”从高到低求解的关键原因。
简单来说，你的算法思路是正确的。这个算法思路的本质是在做记忆化搜索，也就是在做 dp。
下面这个结论是非常关键的，适用于所有的记忆化搜索（或者 dp）问题（是所有）：
记忆化搜索（或者 dp），可以看做是在一张图上做搜索，记忆化搜索（或者 dp）的每一个状态组合，就是图上的一个节点，每一个状态的转移，就是图上的一条有向边。
关键来了：从这个视角看，如果使用记忆化搜索（或者 dp），就要求我上面描述的这张图，是 DAG（有向无环图）。关键不是有向，因为状态转移的方向已经指明了边的方向，所以这样建立的图一定是有向图。关键是“无环”。
为什么要“无环”，也很好理解。记忆化搜索（或者 dp）的本质是根据已知的状态，推导出未知的状态。但如果这张图上有环，就意味着你在试图用未知的状态，推导未知的状态。或者说，要想求 A，需要知道 B，要想求 B，就需要知道 A。这是不可能的。
那么遇到这种情况怎么解决？如果你确定要继续使用记忆化搜索（或者 dp）的思路的话，就需要把环想办法消掉。
注意：
1）不排除问题无法把环消掉，那就意味着对于这个问题来说，是不能使用记忆化搜索或者 dp 解决的。
2）也不排除消环的手段非常“巧妙”，其实本质已经不是在“旧的思路”上消环了，而是对问题重新建模（重新设立状态，重新设立状态转移的方式），在新的问题模型上，整个图中没有环了。
这两种情况如果做过相当数量的 dp 问题，都近乎一定会遇到。但你要让我给你马上找个特别好的例子，我一时也找不到。你可以对此先有个印象，如果你以后接触更多的 dp 问题（尤其是竞赛难度），近乎一定会对此有很深的体会。
==========
说回这个问题，这个问题能不能消环？能。
我能想到的最直接的方式，是使用处理图问题的一个常用的“高级手段”：缩点。（之所以说是“高级手段”，是因为面试不会考察这类问题，但是在算法竞赛中算是一个常用的思路。其实思路并不复杂，实现会稍复杂一些。）
这张图中的环，只会出现在相邻的，相同的高度的节点的位置。我们可以先预处理整张图，把这些相邻的相同节点找到，然后让这些节点“缩成”一个点。这样，这张图中的环就消失了。
在具体实现上，“缩点”的一个常用的实现手段，是使用并查集。把一系列点“并”在一起。这一系列点在并查集中都指向了同一个根节点。用这个根节点，来表示所有这一系列点。也就是把这一系列点，缩成了一个点（根节点）。
具体可以参考我的实现（C++），我加入了一些注释。但还有很多细节，可能如果不亲自动手实现，很难注意到，但整体如果你只是想要一个 idea 的话，大体思路应该能理解：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0417-Pacific-Atlantic-Water-Flow/cpp-0417/main2.cpp
（如果有不理解的细节，可以再追加提问。）
我不排除这个问题如果从高处向低处搜索有更“简洁”的写法。但是整体这个写法对我来讲是思路最清晰的
（熟悉我的同学都知道，我更喜欢追求思路清晰的写法，而非最简洁或者代码行数最少的写法）。
整体思路就是：
1）缩点（59-70 行）
2）根据缩好的点，建新图（DAG）（74-95 行）
3）在新图上记忆化搜索解（100-103 行）
4）根据搜索的结果得到原问题的答案 （105-112 行）
==========
最后你可以看出来，对于这个问题，从高处向低处搜索，难度大了很多。我个人并不推荐这个解法，甚至不认为大家需要掌握这个解法。虽然缩点是一个在某些图论问题中绕不开的技巧，但是用在这个问题上，不值当。
原因很简单，从低向高处搜索，这一切麻烦都没有了。
而实际上，逆向思考本身，是解决很多问题的“经典”做法。这本身是一个值得在处理任何问题上（不仅仅是算法问题，甚至不仅仅是数学类问题），都值得反复提醒自己的思路：如果正着想有难度，想不明白，试一试逆着想，很可能柳暗花明。我认为这个经验，比这个解法本身有意义。
继续加油！：）
112022-08-20
相似问题