934. Shortest Bridge

Medium

Description

給定一個 n x n 的二維網格，恰好包含兩座島嶼（值為 1）。求連接兩座島嶼所需翻轉的最少 0 的數量（即兩島間最短距離）。

Example:

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

Intuition#

DFS 找到第一座島嶼的所有格子，然後用 BFS 從該島嶼向外擴展，直到碰到第二座島嶼。

先用 DFS 找到第一座島嶼，將其所有格子加入 BFS 佇列
多源 BFS 同時從第一座島嶼所有邊界格子向外擴展
第一次碰到第二座島嶼的格子時，擴展層數就是答案

Approaches#

⭐1: DFS 標記 + 多源 BFS#

概念: DFS 標記第一座島嶼，然後多源 BFS 找到第二座島嶼的最短距離
時間複雜度: O(n^2)
空間複雜度: O(n^2)

class Solution {
    fun shortestBridge(grid: Array<IntArray>): Int {
        val n = grid.size
        val queue = ArrayDeque<IntArray>()
        var found = false

        // DFS 找到第一座島嶼並標記為 2
        fun dfs(i: Int, j: Int) {
            if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) return
            grid[i][j] = 2
            queue.add(intArrayOf(i, j))
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        }

        // 找到第一座島嶼
        for (i in 0 until n) {
            if (found) break
            for (j in 0 until n) {
                if (grid[i][j] == 1) {
                    dfs(i, j)
                    found = true
                    break
                }
            }
        }

        // 多源 BFS 擴展
        val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
        var steps = 0
        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val (r, c) = queue.removeFirst()
                for ((dr, dc) in dirs) {
                    val nr = r + dr
                    val nc = c + dc
                    if (nr in 0 until n && nc in 0 until n) {
                        if (grid[nr][nc] == 1) return steps
                        if (grid[nr][nc] == 0) {
                            grid[nr][nc] = 2
                            queue.add(intArrayOf(nr, nc))
                        }
                    }
                }
            }
            steps++
        }
        return -1
    }
}

2: 全部用 BFS#

概念: 用 BFS 替代 DFS 標記第一座島嶼
時間複雜度: O(n^2)
空間複雜度: O(n^2)

class Solution {
    fun shortestBridge(grid: Array<IntArray>): Int {
        val n = grid.size
        val queue = ArrayDeque<IntArray>()
        val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

        // 找到第一座島嶼的起始格子
        outer@ for (i in 0 until n) {
            for (j in 0 until n) {
                if (grid[i][j] == 1) {
                    // BFS 標記整座島嶼
                    val markQueue = ArrayDeque<IntArray>()
                    markQueue.add(intArrayOf(i, j))
                    grid[i][j] = 2
                    while (markQueue.isNotEmpty()) {
                        val (r, c) = markQueue.removeFirst()
                        queue.add(intArrayOf(r, c))
                        for ((dr, dc) in dirs) {
                            val nr = r + dr
                            val nc = c + dc
                            if (nr in 0 until n && nc in 0 until n && grid[nr][nc] == 1) {
                                grid[nr][nc] = 2
                                markQueue.add(intArrayOf(nr, nc))
                            }
                        }
                    }
                    break@outer
                }
            }
        }

        var steps = 0
        while (queue.isNotEmpty()) {
            repeat(queue.size) {
                val (r, c) = queue.removeFirst()
                for ((dr, dc) in dirs) {
                    val nr = r + dr
                    val nc = c + dc
                    if (nr in 0 until n && nc in 0 until n) {
                        if (grid[nr][nc] == 1) return steps
                        if (grid[nr][nc] == 0) {
                            grid[nr][nc] = 2
                            queue.add(intArrayOf(nr, nc))
                        }
                    }
                }
            }
            steps++
        }
        return -1
    }
}

🔑 Takeaways#

Pattern: 多源 BFS – 從整座島嶼同時擴展找最短距離
關鍵技巧: 用值 2 標記第一座島嶼來區分兩座島嶼；多源 BFS 保證找到最短距離