題目
#

leetcode 417 - Pacific Atlantic Water Flow (題目說明請點連結)

題目簡述
#

給一個 m x n 的整數矩陣 heights，其中 heights[i][j] 表示該位置的高度。請找出所有既能流向太平洋又能流向大西洋的位置。
水流只能從高處流向低處或相同高度，且只能流向上下左右四個方向。

範例
#

Example 1:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: 這些位置既能流向太平洋又能流向大西洋。

5 × 5 高度陣列：

┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 2 │ 3 │ 5 │ ← 太平洋邊界
├───┼───┼───┼───┼───┤
│ 3 │ 2 │ 3 │ 4 │ 4 │
├───┼───┼───┼───┼───┤
│ 2 │ 4 │ 5 │ 3 │ 1 │
├───┼───┼───┼───┼───┤
│ 6 │ 7 │ 1 │ 4 │ 5 │
├───┼───┼───┼───┼───┤
│ 5 │ 1 │ 1 │ 2 │ 4 │
└───┴───┴───┴───┴───┘
        ↑
    大西洋邊界

答案位置（既能流向太平洋又能流向大西洋）：
[0,4] [1,3] [1,4] [2,2] [3,0] [3,1] [4,0]

Example 2:

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]
Explanation: 所有位置都能同時流向太平洋和大西洋。

2 × 2 高度陣列：

┌───┬───┐
│ 2 │ 1 │ ← 太平洋邊界
├───┼───┤
│ 1 │ 2 │
└───┴───┘
    ↑
大西洋邊界

答案位置（所有位置都能同時流向太平洋和大西洋）：
[0,0] [0,1] [1,0] [1,1]

解題思路
#

這題要求我們找出所有既能流向太平洋又能流向大西洋的位置。我們可以使用深度優先搜尋（DFS）來解決這個問題，具體方法是從邊界開始反向搜尋，找出所有能到達邊界的位置。

解法
#

DFS

創建兩個布林陣列 pacific 和 atlantic 來記錄每個位置是否能到達對應的海洋
從太平洋邊界（左邊界和上邊界）開始 DFS，標記所有能到達太平洋的位置
從大西洋邊界（右邊界和下邊界）開始 DFS，標記所有能到達大西洋的位置
找出同時能到達兩個海洋的位置

步驟
#

初始化：
- 創建 pacific 和 atlantic 布林陣列
- 設定方向陣列 dirs 表示上下左右四個方向
太平洋邊界 DFS：
- 從左邊界（i, 0）開始 DFS
- 從上邊界（0, i）開始 DFS
大西洋邊界 DFS：
- 從右邊界（i, n-1）開始 DFS
- 從下邊界（m-1, i）開始 DFS
收集結果：
- 找出同時為 true 的位置
- 返回結果列表

例子說明
#

heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 2 │ 3 │ 5 │ ← 太平洋邊界
├───┼───┼───┼───┼───┤
│ 3 │ 2 │ 3 │ 4 │ 4 │
├───┼───┼───┼───┼───┤
│ 2 │ 4 │ 5 │ 3 │ 1 │
├───┼───┼───┼───┼───┤
│ 6 │ 7 │ 1 │ 4 │ 5 │
├───┼───┼───┼───┼───┤
│ 5 │ 1 │ 1 │ 2 │ 4 │
└───┴───┴───┴───┴───┘
        ↑
    大西洋邊界

步驟	操作	pacific 陣列	atlantic 陣列	說明
初始化	-	5x5 全為 false	5x5 全為 false	創建兩個布林陣列
太平洋邊界 DFS	從左邊界開始	標記左邊界可達位置	-	從左邊界開始反向搜尋
太平洋邊界 DFS	從上邊界開始	標記上邊界可達位置	-	從上邊界開始反向搜尋
大西洋邊界 DFS	從右邊界開始	-	標記右邊界可達位置	從右邊界開始反向搜尋
大西洋邊界 DFS	從下邊界開始	-	標記下邊界可達位置	從下邊界開始反向搜尋
收集結果	找出交集	-	-	找出同時為 true 的位置

最終結果： [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

完整程式碼
#

java

class Solution {
    // 矩陣的行數和列數
    int m, n;
    // 記錄每個位置是否能到達太平洋和大西洋
    boolean[][] pacific, atlantic;
    // 四個方向的偏移量：下、上、右、左
    int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.m = heights.length;
        this.n = heights[0].length;
        // 初始化兩個布林陣列
        pacific = new boolean[m][n];
        atlantic = new boolean[m][n];

        // 從太平洋邊界開始 DFS
        for(int i = 0; i < m; i++){
            dfs(heights, i, 0, pacific);    // 左邊界（太平洋）
            dfs(heights, i, n-1, atlantic); // 右邊界（大西洋）
        }
        
        // 從大西洋邊界開始 DFS
        for(int i = 0; i < n; i++){
            dfs(heights, 0, i, pacific);    // 上邊界（太平洋）
            dfs(heights, m-1, i, atlantic); // 下邊界（大西洋）
        }

        // 收集結果：找出同時能到達兩個海洋的位置
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(pacific[i][j] && atlantic[i][j]){
                    ans.add(Arrays.asList(i, j));
                }
            }
        }
        return ans;
    }

    // DFS 方法：從邊界開始反向搜尋
    public void dfs(int[][] heights, int x, int y, boolean[][] visited){
        // 標記當前位置為已訪問
        visited[x][y] = true;
       
        // 嘗試四個方向
        for(int[] dir : dirs){
            int nx = x + dir[0], ny = y + dir[1];

            // 檢查邊界條件和是否已訪問
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || visited[nx][ny] == true){
                continue;
            }

            // 檢查水流方向：只能從高處流向低處或相同高度
            if(heights[nx][ny] >= heights[x][y]){
                dfs(heights, nx, ny, visited);
            }
        }
    }
}