leetcode 417. 太平洋大西洋水流问题_leetcode c++ 417

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

一道DFS的变种题，这种题一看就要用DFS+记忆化搜索，但在边界值设定，返回值，传参等细节上要略加修改。
我的思路是：遍历二维数组，对每个元素进行DFS，一共有四个记号用来代表它能走通的路有哪些，-1代表走不通，0代表大西洋和太平洋都能走通，1代表只能流通到太平洋，2代表只能流通到大西洋。每一层根据下一层反馈回来的数据进行分析，得出本层应该返回的值。
记忆体是work数组，不同于普通记忆化搜索的是，我还设置了一个sign参数来表示此层是否应该装进记忆体。这是为了处理相等的两个元素相互流通的问题。
假设
[4,4,4]
[3,3,3]
[4,4,4]
分析元素matrix[1][2]，肉眼分析，该元素应该是大西洋和太平洋都能走通。但如果在对元素matrix[1][1]进行DFS的时候，就会DFS到matrix[1][2]，我的代码里递归下一层前先将上一层的值更改为了INT_MAX，因此这个时候元素matrix[1][2]，是无法向左流通的，这样它的记号就成了2，如果我们就这样把它装入了记忆体work[1][2]=2；接下来DFS到matrix[1][2]的时候就会直接返回work[1][2]=2;那这就是错误的结果。因此我设置了一个布尔类型参数sign，默认为true，在流向相等元素的时候设置为false，如果本层的sign值为false，那么就不装入记忆体，等遍历到我的时候再来一遍就好。
这样可能没能把记忆体的效果发挥到最高，因此运行时间是48ms，在leetcode里只排27%，但是这只跟最优解法差个常数倍的效率，可见算法的大体思路是没问题的了，如果谁有兴趣优化一下细节，欢迎评论。

class Solution {
private:
    vector<int>xol{0,0,1,-1};
    vector<int>yol{1,-1,0,0};
public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty())
            return {};
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>>work(m,vector<int>(n,INT_MAX));
        vector<pair<int,int>>result;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(DFS(matrix,work,i,j,true)==0){
                    result.push_back({i,j});
                }
            }    
        }
        return result;
    }
    int DFS(vector<vector<int>>& matrix,vector<vector<int>>& work,int x,int y,bool sign){
        if(work[x][y]!=INT_MAX)
            return work[x][y];
        int m=matrix.size();
        int n=matrix[0].size();
        if((x==m-1 || y==n-1) && (x==0 || y== 0))
            return 0;
        set<int>save;
        bool flag=true;
        for(int k=0;k<4;++k){
            int a=xol[k]+x;
            int b=yol[k]+y;
            if(a>=0 && a<m && b>=0 && b<n && matrix[a][b]<=matrix[x][y]){
                if(matrix [a][b]==matrix[x][y])
                    flag=false;
                int temp=matrix[x][y];
                matrix[x][y]=INT_MAX;
                int next=DFS(matrix,work,a,b,flag);
                save.insert(next);
                matrix[x][y]=temp;
            }
        }
        if(save.find(0)!=save.end())
            return sign?work[x][y]=0:0;
        if(save.find(1)!=save.end() && (save.find(2)!=save.end() || x==m-1 || y==n-1))
            return sign?work[x][y]=0:0;
        if((save.find(1)!=save.end() || x==0 || y==0) && save.find(2)!=save.end())
            return sign?work[x][y]=0:0;
        if(save.find(1)!=save.end() || x==0 || y==0)
            return sign?work[x][y]=1:1;
        if(save.find(2)!=save.end() || x==m-1 || y==n-1)
            return sign?work[x][y]=2:2;
        return sign?work[x][y]=-1:-1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56