417. Pacific Atlantic Water Flow - C++ | Runtime 0ms | Beats 100% | 逆向雙 BFS 解法

***此篇文章由 Gemini AI 產生*** # Intuition (思路) 我第一個想法是去檢查每一個格子。從每個格子出發，我都可以做一次搜尋（例如 DFS 或 BFS），來看看是否存在一條路徑可以同時流到太平洋（頂部和左側邊界）和大西洋（底部和右側邊界）。然而，這種做法的效率會非常差，因為我會多次重複計算重疊子問題的路徑，最後很可能會導致「超時 (Time Limit Exceeded)」。 一個好得多的方法是「逆向思考」。與其問「這個格子的水可以流到哪裡？」，不如反過來問「有哪些格子可以流到海洋裡？」。我可以從直接接觸海洋的格子開始，向內陸或「向上游」進行遍歷。任何從海洋邊界出發，只要往等高或更高的地方走就能到達的格子，都代表該格子的水可以「向下流」到那片海洋。 所以，我可以先從所有太平洋邊界的格子開始進行一次搜尋，找出所有能流到太平洋的格子。接著，再從所有大西洋邊界的格子開始做第二次搜尋，找出所有能流到大西洋的格子。最後，兩次搜尋結果中都有出現的格子，就是我們的答案。 # Approach (解題方法) 核心思想是使用兩次獨立的廣度優先搜尋（BFS），來分別找出所有可以流入兩大洋的格子。 1. **從太平洋開始：** * 初始化一個佇列 (queue)，並將所有在第一列和第一行的格子（也就是太平洋邊界）加入佇列中。 * 使用一個 `weight` (權重) 矩陣來追蹤可達性。當我們從太平洋這邊訪問到一個格子時，我們就將它的權重加上 `1`。 * 執行 BFS。從佇列中取出格子並探索其相鄰的格子。我們只能從一個格子 `A` 移動到相鄰的格子 `B`，當且僅當 `height(B) >= height(A)`。這就模擬了從海洋的角度來看，水流「往上游」的情況。 * 第一次 BFS 將會把所有能流到太平洋的格子，其權重都標記為 `1`。 2. **移至大西洋：** * 重新初始化 `visited` 追蹤器（但不清空 `weight` 矩陣）。 * 將所有在最後一列和最後一行的格子（大西洋邊界）加入佇列中。 * 使用同樣的「往上游」邏輯，執行第二次 BFS。 * 這一次，當我們訪問到一個格子時，我們將它的權重加上 `2`。 3. **找出交集：** * 在兩次 BFS 遍歷都完成後，我們遍歷整個 `weight` 矩陣。 * 任何權重等於 `3` 的格子（代表來自太平洋 BFS 的 `1` + 來自大西洋 BFS 的 `2`），就是水可以同時流到兩大洋的格子。 * 我們收集所有這些格子的座標，組成最終的答案。 這種方法透過高效地在單次遍歷中找到每個海洋的可達格子集合，避免了多餘的計算。 # Complexity (複雜度) - Time complexity (時間複雜度): 我們執行了兩次 BFS 遍歷。每一次 BFS 最多只會訪問每個格子和邊一次。最後收集結果的迴圈也會遍歷所有格子。因此，時間複雜度與網格中的格子總數成正比。 $$O(m \times n)$$ 其中 $m$ 是列數，$n$ 是行數。 - Space complexity (空間複雜度): 我們使用了一個 `weight` 矩陣、一個 `visited` 矩陣以及一個 BFS 用的佇列。這些資料結構所需的空間與網格中的格子總數成正比。 $$O(m \times n)$$ # Code (程式碼) ```cpp class Solution { int m, n; // weight[i][j] stores reachability: // 1: can reach Pacific // 2: can reach Atlantic // 3: can reach both array<array<int, 200>, 200> weight{}; array<array<bool, 200>, 200> visited{}; // Helper to add a cell to the queue and mark it inline void enqueue(queue<pair<int, int>>& q, int x, int y, int inc) { weight[x][y] += inc; visited[x][y] = true; q.push({x, y}); } // BFS to find all cells that can flow "down" to the initial set of cells in the queue void bfs(queue<pair<int, int>>& q, vector<vector<int>>& heights, int inc) { array<array<int, 2>, 4> dirs{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}}; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto& d : dirs) { int nx = x + d[0]; int ny = y + d[1]; // Check bounds if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; // If already visited in this specific BFS or water can't flow "uphill" if (visited[nx][ny] || heights[x][y] > heights[nx][ny]) continue; // Enqueue the valid neighbor enqueue(q, nx, ny, inc); } } } public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { m = heights.size(); n = heights[0].size(); queue<pair<int, int>> q; // 1. BFS from Pacific Ocean (top and left borders) for (int i = 0; i < m; ++i) enqueue(q, i, 0, 1); for (int i = 1; i < n; ++i) enqueue(q, 0, i, 1); bfs(q, heights, 1); // Reset visited grid for the second BFS visited = {}; // 2. BFS from Atlantic Ocean (bottom and right borders) for (int i = 0; i < m; ++i) enqueue(q, i, n - 1, 2); for (int i = 0; i < n - 1; ++i) enqueue(q, m - 1, i, 2); bfs(q, heights, 2); // 3. Collect all cells that can reach both oceans (weight == 3) vector<vector<int>> ans; ans.reserve(m + n); // Reserve memory as an optimization for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (weight[i][j] == 3) ans.push_back({i, j}); return ans; } }; ```