417. 太平洋大西洋水流问题/C++

参考：https://blog.csdn.net/qq_41855420/article/details/88744535
分别从太平洋的每个点dfs，并记录
分别从大西洋的每个点dfs，并记录
然后遍历所有点，并查看以上2个记录即可。

class Solution {
    vector<vector<int>> res;
    int row,col;
    int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    map<pair<int, int>, bool> pacificFlag;
    map<pair<int, int>, bool> atlanticFlag;
    
    bool inArea(int x,int y){
        return x>=0 && x<row && y>=0 && y<col;
    }
    
    void dfs(vector<vector<int>>& matrix,map<pair<int, int>, bool>& flag, int x,int y){
        flag[{x,y}]=true;
        for(int i=0;i<4;++i){
            int newX=x+d[i][0];
            int newY=y+d[i][1];
            if(inArea(newX,newY) && matrix[x][y]<=matrix[newX][newY] 
            	&& flag.count({newX,newY})==0){
                flag[{newX,newY}]=true;
                dfs(matrix,flag,newX,newY);
            }
        }
        return;
    }
    
   
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        res.clear();
        row = matrix.size();
        if(row==0)
            return res;
        
        col=matrix[0].size();
        if(col==0)
            return res;
        
        for(int i=0;i<row;++i){
            dfs(matrix,pacificFlag,i,0);
            dfs(matrix,atlanticFlag,i,col-1);
        }
        
        for(int i=0;i<col;++i){
            dfs(matrix,pacificFlag,0,i);
            dfs(matrix,atlanticFlag,row-1,i);
        }
        
        for(int i=0;i<row;++i)
            for(int j=0;j<col;++j)
                if(pacificFlag[{i,j}] && atlanticFlag[{i,j}])
                    res.push_back({i,j});
        return res;
    }
};
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