Pacific Atlantic Water Flow (Lee

G家的一道面试题，主要考搜索。方法是，由出口逆向进行搜索。分别找到属于Pacific和Atlantic的两个集合，然后再取交集。

BFS:

class Solution {
public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<pair<int, int>> ret;
        if(matrix.empty() || matrix[0].empty()) return ret;
        int row = matrix.size(), col = matrix[0].size();
        
        vector<vector<bool>> belongPacific(row, vector<bool>(col, false));
        vector<vector<bool>> belongAtlantic(row, vector<bool>(col, false));
        
        findUnion(matrix, belongPacific, 0);
        findUnion(matrix, belongAtlantic, 1);
        
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(belongPacific[i][j] && belongAtlantic[i][j]){
                    ret.push_back({i, j});}
            }
        }
        return ret;
    }
    
    void findUnion(vector<vector<int>>& matrix, vector<vector<bool>> &visited, int idx){
        int row = matrix.size(), col = matrix[0].size();
        queue<pair<int, int>> q;
        switch(idx){
            case 0:
               for(int i=0; i<row; i++){
                   visited[i][0] = true;
                   q.push({i, 0});
               }
               for(int i=0; i<col; i++){
                   visited[0][i] = true;
                   q.push({0, i});
               }
               break;
            case 1:
                for(int i=0; i<row; i++){
                   visited[i][col-1] = true;
                    q.push({i, col-1});
               }
               for(int i=0; i<col; i++){
                   visited[row-1][i] = true;
                   q.push({row-1, i});
               }
               break;
        }
        vector<pair<int, int>> directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        while(!q.empty()){
            int i = q.front().first, j = q.front().second;
            q.pop();
            for(auto it : directions){
                int x = i + it.first, y = j + it.second;
                if(x < 0 || x >= row || y < 0 || y >= col) continue;
                if(!visited[x][y] && matrix[x][y] >= matrix[i][j]){
                    visited[x][y] = true;
                    q.push({x, y});
                }
            }
            
        }
    }
};