題目描述:給定 m×n 高度矩陣,太平洋在左/上邊,大西洋在右/下邊,水往低處流。找出所有既能流到太平洋又能流到大西洋的格子。
解題思路:反向思考:從兩個海洋的邊界出發,「逆流而上」(向更高或相同高度的格子傳播)進行 BFS/DFS。分別標記能到達太平洋和大西洋的格子,兩個集合的交集即為答案。這樣避免了從每個格子出發的暴力搜尋。
時間複雜度:O(m × n) — 每個格子最多被兩個 BFS 各訪問一次。
空間複雜度:O(m × n) — 兩個訪問標記矩陣和佇列。
1. Initialize two BFS queues: pacific (left+top borders) and atlantic (right+bottom borders) 2. BFS from pacific borders, mark reachable cells (water flows uphill in reverse) 3. BFS from atlantic borders, mark reachable cells 4. Collect all cells marked reachable from both oceans 5. Return result
單一 DFS 從所有陸地 O(m×n) 最壞:逐一 DFS 各格檢查雙向流 — 重複計算。
BFS 從邊界逆向 O(m×n):改為從太平洋和大西洋邊界逆向 BFS(沿著水流反向),找交集 — 此即本方法。