image.png

思路1：BFS

  • 此题为经典DFS、经典BFS问题
  • 从低往高，从边缘往中间进行搜索LC417. 太平洋大西洋水流问题
  • 这个解法是参考了大佬的，亮点主要包括以下几点：
    • 利用|= 1; |= 2这样的手段去记录状态矩阵，非常简洁
    • BFS的起始点设置了很多个，这样可以加快遍历速度
    • 利用状态矩阵前后数值是否一致，去判断是否需要加入队列（在加入队列的时候设置去重的检验）
    • 将valid(x, y)函数独立到外部，写法简洁易懂。

      代码1：BFS

  1. class Solution {
  2. public:
  3.     int dx[4] = {0, 1, -1, 0};
  4.     int dy[4] = {1, 0, 0, -1};
  6.     bool valid(int x, int y, int row, int col) {
  7.         if (x < 0 || x >= row) {
  8.             return false;
  9.         }
  10.         if (y < 0 || y >= col) {
  11.             return false;
  12.         }
  13.         return true;
  14.     }
  16.     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
  17.         int row = heights.size(), col = heights[0].size();
  18.         vector<vector<int>> rec(row, vector<int>(col, 0));
  20.         queue<pair<int, int>> q;
  21.         // 初始队列需要放进去很多东西，同时，需要在入队时设置矩阵状态，避免重复遍历
  22.         for (int i = 0; i < row; ++i) {
  23.             q.push(make_pair(i, 0));
  24.             rec[i][0] |= 1;
  25.             q.push(make_pair(i, col - 1));
  26.             rec[i][col - 1] |= 2;
  27.         }
  29.         // p:01   A:10
  30.         // 重复放也不要怕，进入队列的时候有去重的检验手段了
  31.         for (int i = 0; i < col; ++i) {
  32.             q.push(make_pair(0, i));
  33.             rec[0][i] |= 1;
  34.             q.push(make_pair(row - 1, i));
  35.             rec[row - 1][i] |= 2;
  36.         }
  38.         while (!q.empty()) {
  39.             pair<int, int> cur_node = q.front();
  40.             q.pop();
  42.             int cur_x = cur_node.first, cur_y = cur_node.second;
  44.             for (int i = 0; i < 4; ++i) {
  45.                 int nxt_x = cur_x + dx[i], nxt_y = cur_y + dy[i];
  46.                 if (!valid(nxt_x, nxt_y, row, col)) {
  47.                     continue;
  48.                 }
  49.                 if (heights[nxt_x][nxt_y] < heights[cur_x][cur_y]) {
  50.                     continue;
  51.                 }
  52.                 // 说明已经访问过了
  53.                 if (rec[nxt_x][nxt_y] == rec[cur_x][cur_y]) {
  54.                     continue;
  55.                 }
  56.                 q.push(make_pair(nxt_x, nxt_y));
  57.                 rec[nxt_x][nxt_y] |= rec[cur_x][cur_y];
  58.             }
  59.         }
  61.         vector<vector<int>> ans;
  62.         for (int i = 0; i < row; ++i) {
  63.             for (int j = 0; j < col; ++j) {
  64.                 // P:01 A:10 both:11
  65.                 if (rec[i][j] == 3) {
  66.                     ans.push_back({i, j});
  67.                 }
  68.             }
  69.         }
  71.         return ans;
  72.     }
  73. };

思路2：DFS todo