具有循环依赖的 DFS

Question

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

这是我的解决方案

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

您在实施过程中遇到了多个问题：

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

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

计算一个单元格是否被太平洋触及
计算单元格是否被大西洋触及

但是对于单个 DFS，您可以在前向路径上更新一个属性，而第二个只能在遍历的后向路径上更新。

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

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

在两次洪水填充之后，您最终输出了两个海洋接触过的所有单元格。 Flood-fill 是 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;
}

具有循环依赖的 DFS

DFS with cyclic dependency

algorithm

matrix

depth-first-search

breadth-first-search