LeetCode 题解工作台
最短的桥
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地， 0 表示水域。 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。 grid 中 恰好存在两座岛 。 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。 返回必须翻转的 0 的…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
题目求解的是最小翻转次数，使得两个岛屿相连，实际上等价于求解两个岛屿之间的最短距离。 因此，我们可以先通过 DFS 将其中一个岛屿的所有点找出来，放到一个队列 中。然后通过 BFS 一层层向外扩展，直至碰到另一个岛屿，此时将当前扩展的层数作为答案返回即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 1：
输入：grid = [[0,1],[1,0]] 输出：1
示例 2：
输入：grid = [[0,1,0],[0,0,0],[0,0,1]] 输出：2
示例 3：
输入：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]] 输出：1
提示：
n == grid.length == grid[i].length2 <= n <= 100grid[i][j]为0或1grid中恰有两个岛
解题思路
方法一：DFS + BFS
题目求解的是最小翻转次数，使得两个岛屿相连，实际上等价于求解两个岛屿之间的最短距离。
因此，我们可以先通过 DFS 将其中一个岛屿的所有点找出来，放到一个队列 中。然后通过 BFS 一层层向外扩展，直至碰到另一个岛屿，此时将当前扩展的层数作为答案返回即可。
在 DFS 和 BFS 搜索的过程中，我们直接将已经访问过的点标记为 ，这样就不会重复访问。
时间复杂度 ，空间复杂度 。其中 为矩阵的行数或列数。
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
def dfs(i, j):
q.append((i, j))
grid[i][j] = 2
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
dfs(x, y)
n = len(grid)
dirs = (-1, 0, 1, 0, -1)
q = deque()
i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])
dfs(i, j)
ans = 0
while 1:
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n:
if grid[x][y] == 1:
return ans
if grid[x][y] == 0:
grid[x][y] = 2
q.append((x, y))
ans += 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) because DFS visits all cells of the first island and BFS potentially visits every cell in the grid. Space complexity is O(n^2) to store visited flags and the BFS queue for the island boundaries. |
| 空间 | O(n^2) |
面试官常问的追问
外企场景- question_mark
Expect you to recognize the two-island pattern in the grid and articulate an efficient search strategy.
- question_mark
They may hint at using DFS first to mark the island before attempting BFS expansion.
- question_mark
They look for correct distance measurement while handling matrix boundaries and visited checks.
常见陷阱
外企场景- error
Failing to mark visited cells can cause infinite loops or incorrect distance calculation.
- error
Expanding BFS incorrectly may overshoot the shortest path or revisit the first island.
- error
Not handling edge boundaries leads to index errors in matrix traversal.
进阶变体
外企场景- arrow_right_alt
Compute shortest bridge in non-square grids with different numbers of islands.
- arrow_right_alt
Return all possible shortest paths connecting two islands instead of just the count.
- arrow_right_alt
Find minimal bridge while allowing diagonal connections between islands.