LeetCode417.太平洋大西洋水流问题

Question

老师，可以帮忙看看代码问题吗？我感觉思路没有问题，但是过不了。
我的思路：遍历每一个点，对每一个点都进行dfs,如果a 和 b都是true，说明两个海洋都可以流入。。。。

class Solution {
public:
    int idx[4] = {-1, 0, 1, 0};
    int idy[4] = {0, 1, 0, -1};
    
    vector<vector<bool>> book; //记录某个结点是否遍历过
    int n;  //点数
    bool a = false, b = false; // 是否可流入pacific, 是否流入atlantic

    void dfs(vector<vector<int>>& heights, int x, int y) {
        book[x][y] = true;
        for(int i = 0; i < 4; i++) {

            int newx = idx[i] + x, newy = idy[i] + y;

            if(newx < 0 || newy < 0){  a = true;  continue;  }//进入了pacific
            if(newx >= n || newy >= n){  b = true;   continue; }//进入入了atlantic

            if(heights[x][y] > heights[newx][newy] && !book[newx][newy])
                dfs(heights, newx, newy);
        }
        book[x][y] = false;
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        //数组的初始化
        n = heights.size();
        book = vector<vector<bool>>(n, vector<bool>(n, false));
        vector<vector<int>> res;

        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++){
                dfs(heights, i, j);
                if(a && b)  res.push_back( {i, j} );
                a = b = false;
            }

        return res;
    }
};

Answer 1

liuyubobobo 2022-04-29 02:16:12

你现在的代码的核心逻辑问题是：题目中的要求，如果相邻格子的高度是相同的，水依然可以流过去。但是你的逻辑只有 heights[x][y] > heights[newx][newy] 才可以流过去。

应该是：heights[x][y] >= heights[newx][newy]

但是你的代码，如果修改成 heights[x][y] >= heights[newx][newy]，依然会有问题。

出问题的测试用例是如果所有格子都相同。可以测试一下，然后再思考一下如何解决？

==========

另：你的这个思路即使走通了，也很有可能 tle。假设整个 grid 是 n*n 的。对每一个点做一遍 dfs，每一次 dfs 都是 n*n 的，整体就是 n^4 的。对于 n = 200，n^4 就是1.6 * 10^9，这个规模是很高的。

这个问题更好的解决方案是，反向的，从太平洋或者大西洋的水“逆流”去看能逆着走到哪里。如果一个格子既能从大西洋逆流流到，又能从太平洋逆流留到，则这个格子可以放入 res 中。

参考代码（Java 的，但应该很好理解）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0417-Pacific-Atlantic-Water-Flow/java-0417/src/Solution.java

继续加油！：）

• 提问者 慕盖茨3358155 #1

  谢谢老师，已经解决了~