給定一個
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
TIP
DFS 找到第一座島嶼的所有格子，然後用 BFS 從該島嶼向外擴展，直到碰到第二座島嶼。
- 先用 DFS 找到第一座島嶼，將其所有格子加入 BFS 佇列
- 多源 BFS 同時從第一座島嶼所有邊界格子向外擴展
- 第一次碰到第二座島嶼的格子時，擴展層數就是答案
Approaches
⭐ 1. DFS Marking + Multi-Source BFS — O(n^2) / O(n^2)
- Idea: DFS 標記第一座島嶼，然後多源 BFS 找到第二座島嶼的最短距離
- Time:
O(n^2) - Space:
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. All-BFS — O(n^2) / O(n^2)
- Idea: 用 BFS 替代 DFS 標記第一座島嶼
- Time:
O(n^2) - Space:
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 — 從整座島嶼同時擴展找最短距離
- Key trick: 用值
2標記第一座島嶼來區分兩座島嶼；多源 BFS 保證找到最短距離