2026/04/30

[LeetCode] 417 Pacific Atlantic Water Flow

原本以為跟經典的滑雪一樣, 可以dfs/dp互通

結果這題的「小於等於」會破壞dp的方向性

所以只能改從終點往回走, 只能視為單純的flood fill

想歪了兩天, 挺有趣的

 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
55
56
57
class Solution {
private:
  static constexpr int SIZE = 201;
  int N, M;
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {1, 0, -1, 0};

  void bfs(std::queue<pair<int, int>>& Q, 
           bool (&vis)[SIZE][SIZE],
           vector<vector<int>>& heights) {
    while(!Q.empty()) {
      int x = Q.front().first;
      int y = Q.front().second;
      Q.pop();
      
      vis[x][y] = true;
      for (int i = 0; i < 4; i++) {
        int dx = x + dirX[i];
        int dy = y + dirY[i];
        if (dx >= 0 && dx < N && dy >= 0 && dy < M)
          if (!vis[dx][dy] && heights[x][y] <= heights[dx][dy])
            Q.push(std::make_pair(dx, dy));
      }
    }
  }

public:
  vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    N = heights.size();
    M = heights[0].size();
    
    bool visP[SIZE][SIZE] = {0};
    bool visA[SIZE][SIZE] = {0};
    std::queue<pair<int, int>> paQ;
    std::queue<pair<int, int>> atQ;

    for(int i = 0; i < N; i++) {
      paQ.push(std::make_pair(i, 0));
      atQ.push(std::make_pair(i, M - 1));
    }

    for(int i = 0; i < M; i++) {
      paQ.push(std::make_pair(0, i));
      atQ.push(std::make_pair(N - 1, i));
    }

    bfs(paQ, visP, heights);
    bfs(atQ, visA, heights);

    vector<vector<int>> ans;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++)
        if (visP[i][j] && visA[i][j])
          ans.push_back({i, j});
    return ans;
  }
};
Labels: