417. Pacific Atlantic Water Flow

起初我就是從兩個邊的所有點, 分成兩個bfs進行, 先標記太平洋的範圍, 在標記大西洋的範圍, 最後兩個都有被算到的就是我們要的點

另外題目範例的那個括號要表示的是這個點符合通往大西洋跟太平洋

class Solution {
public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {
    int m = matrix.size();
    if(m == 0 ) return {};
    int n = matrix[0].size();
    if(n == 0) return {};
    vector<vector<pair<bool, bool>>> dp(m, vector<pair<bool, bool>> (n, {false, false}));
    queue<pair<int, int>> q1;
    queue<pair<int, int>> q2;
for(int i = 0; i < m;i++){
      q1.push({i, 0});
      q2.push({i, n - 1});
    }
    for(int j = 0; j < n;j++){
      q1.push({0, j});
      q2.push({m - 1, j});
    }
    set<pair<int, int>> st;
    vector<vector<int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    // paicifc
    while(!q1.empty()){
      auto cur = q1.front();
      int cur_i = cur.first;
      int cur_j = cur.second;
      dp[cur_i][cur_j].first = true;
      q1.pop();
      for(auto dir: dirs){
        int x = cur_i + dir[0];
        int y = cur_j + dir[1];
        if(x < 0 || x >= m || y < 0 || y >= n || dp[x][y].first == true){
          continue;
        }
        if(matrix[x][y] >= matrix[cur_i][cur_j])
          q1.push({x, y});
      }
    }
    while (!q2.empty()) {
      auto cur = q2.front();
      int cur_i = cur.first;
      int cur_j = cur.second;
      dp[cur_i][cur_j].second = true;
      if(dp[cur_i][cur_j].first == true){
        st.insert({cur_i, cur_j});
      }
      q2.pop();
      for (auto dir : dirs) {
        int x = cur_i + dir[0];
        int y = cur_j + dir[1];
        if (x < 0 || x >= m || y < 0 || y >= n || dp[x][y].second == true) {
          continue;
        }
        if (matrix[x][y] >= matrix[cur_i][cur_j])
          q2.push({x, y});
      }
    }
    vector<vector<int>> res;
    for(auto i: st){
      res.push_back({i.first, i.second});
    }
    return res;
  }
};