algorithm - 具有循环依赖的 DFS

Question

我试图解决 this challenge

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

您在实现中遇到多个问题:

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

你的 dp 的原因gray 的数组未正确更新cells 是你尝试同时做两件事:

1. 计算细胞是否被太平洋接触
2. 计算细胞是否被大西洋接触

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

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

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

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

在我的实现中，我开始 n+m洪水淹没了每个海洋，但我保持不变visiteds map ，所以它仍然保留在 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;
}