老师能否帮我看下LeetCode417大西洋水流问题

Question

老师您好，这道题是我看了老师的第8-7讲做的。思路是按照DFS的思路，仿照了200题岛屿问题的代码。从可以到达大西洋或者太平洋边上的点进行DFS搜索，满足条件的都保存为true。最后取交集得到结果。现在DFS函数中显示会出现两个点来回跳跃的情况。我参考的一个LeetCode题解也是这个思路，我看感觉代码的写法虽然不一样，思路上是一样的。他的就可以跑通，感觉很疑惑。没有感觉到有什么区别，希望老师帮看下我的问题在哪里。如果老师也有自己的LeetCode github代码，求一下链接。
我自己的会堆栈溢出的代码如下：`class Solution {
int d[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};

bool IfValid(const vector<vector<int>>& matrix, int x, int y)
{
    if( x<0 || x>=matrix.size() || y<0 || y>=matrix[0].size())
    {
        return false;
    }
    return true;

}
void DFS(const vector<vector<int>>& matrix,const int x,const int y,vector<vector<bool>>& res)
{
    res[x][y] = true;
    
    for(int i=0;i<4;i++)
    {
        int newx = x+d[i][0];
        int newy = y+ d[i][1];

        if(IfValid(matrix,newx,newy) && matrix[newx][newy] >= matrix[x][y])
        {
            cout<<"newx="<<newx<<"newy="<<newy<<endl;
            DFS(matrix,newx,newy,res);
        }
    }
    return;
}

public:
vector<vector> pacificAtlantic(vector<vector>& matrix) {
vector<vector> positionResult;
int height = matrix.size();
if(height == 0) return positionResult;
int length = matrix[0].size();
vector<vector> toTai(height,vector(length,false));
vector<vector> toDa(height,vector(length,false));

    //利用DFS的方式从边上开始遍历完成
    for( int i=0;i<height;i++)
    {
        DFS(matrix,i,0, toTai);
        DFS(matrix,i,length-1,toDa);
    }
    for(int i=0; i<length;i++)
    {
        DFS(matrix,0,i,toTai);
        DFS(matrix,height-1,i,toDa);
    }

    //去交集
    for(int i=0; i<height; i++)
    {
        for(int j=0; j<length; j++)
        {
            if(toDa[i][j] && toTai[i][j])
            {
                vector<int> one;
                one.push_back(i);
                one.push_back(j);
                positionResult.push_back(one);
            }
        }
    }

    return positionResult;
}

};`

我参考的可以跑通的代码如下：

class Solution {
public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        vector<pair<int, int>> res;
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i) {
            dfs(matrix, pacific, INT_MIN, i, 0);
            dfs(matrix, atlantic, INT_MIN, i, n - 1);
        }
        for (int i = 0; i < n; ++i) {
            dfs(matrix, pacific, INT_MIN, 0, i);
            dfs(matrix, atlantic, INT_MIN, m - 1, i);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    res.push_back({i, j});
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int pre, int i, int j) {
        int m = matrix.size(), n = matrix[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || matrix[i][j] < pre) return;
        visited[i][j] = true;
        dfs(matrix, visited, matrix[i][j], i + 1, j);
        dfs(matrix, visited, matrix[i][j], i - 1, j);
        dfs(matrix, visited, matrix[i][j], i, j + 1);
        dfs(matrix, visited, matrix[i][j], i, j - 1);
    }
};

Answer 1

liuyubobobo 2020-03-14 14:19:51

要解决你现在的无限递归的问题，你需要在 DFS 的递归调用前的那个判断，加上对 res 的判断，即：

if( IfValid(matrix,newx,newy) && 
    matrix[newx][newy] >= matrix[x][y] && 
    !res[newx][newy]){ // 这里！！！
    // cout<<"newx="<<newx<<"newy="<<newy<<endl;
    DFS(matrix,newx,newy,res);
}

不然的话，你的 res 只是在 dfs 中做了一下赋值，没有被使用。

继续加油！：）