題目
#

leetcode 934 - Shortest Bridge (題目說明請點連結)

題目簡述
#

給定一個二維網格，包含兩個島嶼（由相連的陸地組成），找到連接兩個島嶼的最短橋樑長度。橋樑只能在水面上建造。

範例
#

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1
Explanation: 需要建造一座橋樑連接兩個島嶼，最短距離為 1。

Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Explanation: 需要建造一座橋樑連接兩個島嶼，最短距離為 2。

Example 3:

Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
Explanation: 兩個島嶼之間的最短距離為 1。

解題思路
#

這題要求我們找到連接兩個島嶼的最短橋樑長度。島嶼由相連的陸地（1）組成，海洋由水（0）表示。

問題分析
#

給定一個二維網格，包含兩個島嶼
需要找到連接兩個島嶼的最短橋樑
橋樑只能在水面上建造
返回最短橋樑的長度

解法：DFS + BFS
#

DFS：用於標記第一個島嶼的所有陸地
BFS：用於計算從第一個島嶼到第二個島嶼的最短距離
邊界處理：確保只在水面上建造橋樑

步驟：
#

找到第一個島嶼
- 使用 DFS 遍歷第一個島嶼的所有陸地
- 將第一個島嶼的所有邊界點加入佇列
找到第二個島嶼
- 使用 BFS 從第一個島嶼的邊界開始擴展
- 計算到第二個島嶼的最短距離

例子說明
#

輸入： grid = [[0,1],[1,0]]

步驟 1：找到第一個島嶼

從 (0,1) 開始 DFS
標記第一個島嶼的所有陸地
將邊界點加入佇列

步驟 2：BFS 尋找第二個島嶼

從佇列中的點開始擴展
計算到第二個島嶼的距離

答案： 1（最短橋樑長度）

完整程式碼
#

java

import java.util.*;

class Solution {
    // 四個方向的移動：上、下、左、右
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int shortestBridge(int[][] grid) {
        int m = grid.length, n = grid[0].length; // 網格的行數和列數
        boolean[][] visited = new boolean[m][n]; // 記錄已訪問的點
        boolean flag = false; // 標記是否已找到第一個島嶼
        Queue<int[]> queue = new LinkedList<>(); // 用於BFS的佇列

        // 使用DFS找到第一個島嶼，並將其邊界點加入佇列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // 找到第一個陸地
                    dfs(grid, i, j, queue, visited); // 使用DFS標記第一個島嶼
                    flag = true; // 標記已找到第一個島嶼
                    break; // 跳出內層迴圈
                }
            }
            if (flag) { // 如果已找到第一個島嶼，跳出外層迴圈
                break;
            }
        }

        // 使用BFS找到到第二個島嶼的最短距離
        int distance = 0; // 記錄橋樑的長度
        while (!queue.isEmpty()) {
            int size = queue.size(); // 當前層的點數

            // 處理當前層的所有點
            for (int s = 0; s < size; s++) {
                int[] cur = queue.poll(); // 取出佇列中的點
                int x = cur[0], y = cur[1]; // 當前點的座標

                // 檢查四個方向
                for (int[] dir : dirs) {
                    int i = x + dir[0], j = y + dir[1]; // 相鄰點的座標
                    // 檢查邊界條件和是否已訪問
                    if (i >= 0 && i < m && j >= 0 && j < n && !visited[i][j]) {
                        if (grid[i][j] == 1) { // 如果遇到第二個島嶼的陸地
                            return distance; // 返回當前距離
                        }

                        queue.offer(new int[]{i, j}); // 將相鄰點加入佇列
                        visited[i][j] = true; // 標記為已訪問
                    }
                }
            }
            distance++; // 橋樑長度加1
        }

        return -1; // 如果無法連接兩個島嶼，返回-1
    }

    // DFS方法：標記第一個島嶼的所有陸地
    public void dfs(int[][] grid, int i, int j, Queue<int[]> queue, boolean[][] visited) {
        // 檢查邊界條件和是否已訪問或為水
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || visited[i][j] || grid[i][j] == 0) {
            return;
        }

        queue.offer(new int[]{i, j}); // 將當前點加入佇列
        visited[i][j] = true; // 標記為已訪問

        // 遞迴訪問四個方向的相鄰點
        for (int[] dir : dirs) {
            dfs(grid, i + dir[0], j + dir[1], queue, visited);
        }
    }
}