具有循环依赖关系的 DFS

Question

我试图解决这个挑战

给定一个表示高度的非负整数的 m x n 矩阵 在一个大陆的每个晶胞中，"太平洋"触及左侧 矩阵的顶部边缘和"大西洋"接触右侧 和底部边缘。

水只能从四个方向(向上、向下、向左或向右)流动 一个单元格到另一个高度等于或更低的单元格。

查找水可以流向两者的网格坐标列表 太平洋和大西洋。

注意：返回的网格坐标的顺序无关紧要。都 m 和 n 小于 150。

例：

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).

这是我的解决方案

class Solution {
public:
vector<pair<int, int>> result;
map<pair<int, int>, pair<bool, bool>> dp;
//    P     A
pair<bool, bool> doPacific(vector<vector<int>>& matrix, vector<vector<bool>> & visited,  int row, int col)
{
cout << row << ' ' << col << endl;
if(col < 0 || row < 0)
{
return pair<bool, bool>(true, false);
}
if(col >= matrix[0].size() || row >= matrix.size())
{
return pair<bool, bool>(false, true);
}
if(visited[row][col])
{
return dp[make_pair(row, col)];
}
pair<bool,bool> left(false, false);
pair<bool,bool> right(false, false);
pair<bool,bool> top(false, false);
pair<bool,bool> bottom(false, false);
visited[row][col] = true;
// Go Down if index is invalid or has valid index and water level
if(((row + 1 < matrix.size()) && (matrix[row + 1][col] <= matrix[row][col])) || row + 1 >= matrix.size())
{
bottom = doPacific(matrix,visited, row + 1, col);
}
if(((row - 1 >= 0) && (matrix[row - 1][col] <= matrix[row][col])) || (row -1 < 0))
{
top = doPacific(matrix,visited, row - 1, col);
}
if(((col + 1 < matrix[0].size()) && (matrix[row][col + 1] <= matrix[row][col])) || (col + 1>= matrix[0].size()))    
{
right = doPacific(matrix,visited, row, col + 1);
}
if(((col - 1 >=0) && (matrix[row][col - 1] <= matrix[row][col])) || (col -1 < 0))
{
left = doPacific(matrix,visited, row, col - 1);
}
pair<bool, bool>returnValue(false, false);
returnValue.first |= left.first;
returnValue.second |= left.second;
returnValue.first |= right.first;
returnValue.second |= right.second;
returnValue.first |= bottom.first;
returnValue.second |= bottom.second;
returnValue.first |= top.first;
returnValue.second |= top.second;
dp.insert(make_pair(make_pair(row, col), returnValue));
if(returnValue.first && returnValue.second)
{
result.push_back(make_pair(row, col));
}
return returnValue;
}
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
result.clear();
dp.clear();
for(int i=0; i< matrix.size(); ++i)
{
for(int j=0; j < matrix[0].size(); ++j)
{
if(!visited[i][j])
{
doPacific(matrix, visited, i, j); 
}                
}
}
return result;
}
};

但是我的解决方案无法输入

[10,10,10]
[10, 1,10]
[10,10,10]

我的回答只省略了索引(0,1).

当我跟踪递归树时，它看起来像这样。

(0, 0)
/
(1,0)
/
(2, 0)
/   
(2, 1)  (2, 2)
/      /
(T,F)/    (1,2)
(1, 1)     /
(0,2)
/
(0,1) This return(T,F) when it should return (T,T).
Because (0,1) won't call (0,0) since it is 
already being processed(i.e visited) which in turn depends on (0,1), 
creating a cycle. Although there exists a path 
from (0,0) to atlantic

我的问题是，当现有节点和要添加的节点之间存在循环依赖关系时，我该如何解决这种情况。

处理此类问题的方法不正确吗？

Answer 1

您的实现中存在多个问题：

1. 您只考虑节点的两种状态：not visited和visited。但你确实可以陷入第三种状态。通常我们考虑颜色white、gray和black。在代码中，gray和black颜色以单个visited状态合并在一起。
2. 输入新节点时，如果将该节点标记为visited则不会再次访问它，而只需在dp数组中查找其值。正如您发现自己的那样，它不起作用，因为dp数组仅适用于black单元格，而不适用于gray单元格。但是因为问题1。你无法做出改变

dp数组未针对gray单元格正确更新的原因是您尝试同时执行两件事：

1. 计算单元格是否被太平洋触摸
2. 计算单元格是否被大西洋接触

但是，使用单个 DFS，可以在正向路径上更新一个属性，而仅在遍历的后向路径上更新第二个属性。

解决方案是使用两个 DFS 分别更新每个属性。

您可以尝试从一个海洋开始，然后从第二个海洋开始进行两次洪水填充，而不是单个DFS。每个洪水填充都是一个DFS，但来自不同的来源，并更新不同的visited属性。显然，你颠倒了水流的条件，即你的水从低海拔流向高海拔。

在两次洪水填充之后，您最终会输出两个海洋接触的所有单元格。泛洪填充是O(n*m)因此与当前实现相比，它不会降低复杂性。

在我的实现中，我开始为每个海洋n+m洪水填充，但我保留相同的visiteds地图，因此它仍然保留在O(n*m)

下面是一个示例解决方案(可读，但仍比 91% 的 c++ 提交更快)。看到我使用位屏蔽技术来标记海洋(1 -> 太平洋、2 -> 大西洋、3 -> 两者)访问的单元格，而不是pair<bool,bool>但这只是为了性能优化。

int width, height;
vector<vector<unsigned char>> visiteds;
void floodFill(int i, int j, unsigned char mask, vector<vector<int>>& matrix) {
visiteds[i][j] = visiteds[i][j] | mask;
auto& h = matrix[i][j];
if(i > 0 && matrix[i-1][j] >= h && !(visiteds[i-1][j] & mask))
floodFill(i-1, j, mask, matrix);
if(i < height-1 && matrix[i+1][j] >= h && !(visiteds[i+1][j] & mask))
floodFill(i+1, j, mask, matrix);
if(j > 0 && matrix[i][j-1] >= h && !(visiteds[i][j-1] & mask))
floodFill(i, j-1, mask, matrix);
if(j < width-1 && matrix[i][j+1] >= h && !(visiteds[i][j+1] & mask))
floodFill(i, j+1, mask, matrix);
}
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int>> cells;
height = matrix.size();
if(! height)
return cells;
width = matrix[0].size();
visiteds.clear();
visiteds.resize(height, vector<unsigned char>(width, 0));
for(int k=0; k<height; ++k) {
floodFill(k, 0, 1, matrix);
floodFill(k, width-1, 2, matrix);
}
for(int k=0; k<width; ++k) {
floodFill(0, k, 1, matrix);
floodFill(height-1, k, 2, matrix);
}
for(size_t i=0; i<height; ++i)
for(size_t j=0; j<width; ++j)
if(visiteds[i][j] == 3)
cells.push_back(make_pair(i, j));
return cells;
}