leetcode 417. 太平洋大西洋水流问题（C++）

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

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

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

提示：

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

示例：

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

C++

class Solution {
public:
    void bfs(queue<pair<int,int>>& que, vector<vector<int>>& flag, vector<vector<int>>& matrix) {
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};
        while(!que.empty()) {
            auto it=que.front();
            que.pop();
            int i=it.first;
            int j=it.second;
            for(int k=0;k<4;k++) {
                int y=i+dy[k];
                int x=j+dx[k];
                if(y>=0 && y<matrix.size() && x>=0 && x<matrix[0].size() && 0==flag[y][x] && matrix[y][x]>=matrix[i][j]) {
                    flag[y][x]=1;
                    que.push({y,x});
                }
            }
        }        
    }
    
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> res;
        if(0==matrix.size() || 0==matrix[0].size()) {
            return res;
        }
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>> flag(m,vector<int>(n,0));
        queue<pair<int,int>> que;
        for(int i=0;i<m;i++) {
            flag[i][0]=1;
            que.push({i,0});
        }
        for(int i=1;i<n;i++) {
            flag[0][i]=1;
            que.push({0,i});
        }
        bfs(que,flag,matrix);
        vector<vector<int>> vec(m,vector<int>(n,0));
        for(int i=0;i<m;i++) {
            vec[i][n-1]=1;
            que.push({i,n-1});
        }
        for(int i=0;i<n-1;i++) {
            vec[m-1][i]=1;
            que.push({m-1,i});
        }
        bfs(que,vec,matrix);
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(flag[i][j] && vec[i][j]) {
                    res.push_back({i,j});
                }
            }
        }
        return res;
    }
};