LeetCode 934. 最短的桥 题目描述 在给定的一个大小为 n x n 的二进制矩阵 grid 中，恰好存在两座“岛屿”（由若干 1 组成，表示陆地， 0 表示海洋）。你可以将任意数量的海洋格子变为陆地格子，使得两座岛屿连接起来。返回必须翻转（即从海洋变为陆地）的最小海洋格子数目，以使两座岛屿相连。可以保证答案至少是 1。 示例 1 输入：grid = [ [ 0,1],[ 1,0] ] 输出：1 示例 2 输入：grid = [ [ 0,1,0],[ 0,0,0],[ 0,0,1] ] 输出：2 约束条件 n == grid.length == grid[ i ].length 2 <= n <= 100 grid[ i][ j ] 只能是 0 或 1 grid 中恰好有两个岛屿 解题过程循序渐进讲解 第一步：理解问题的核心 题目中矩阵恰好有两个由“1”组成的连通块（即两座岛屿）。我们需要找到最短的路径，用“0”填海造陆（将0变为1），使得这两个岛屿连通。注意，填海时只能将原本是0的格子变为1，且填海的格子必须是连续的（四连通方向），最终连接两个岛屿。这本质上是求两个连通块之间的最短距离，距离定义为需要翻转的0的个数。 第二步：问题转化与思路 先通过DFS或BFS找到其中一座岛屿的所有陆地格子，并标记出来（例如标记为2），这样我们就区分了两个岛屿。 然后从这座岛屿的所有边界格子（即岛屿的边缘格子）开始，进行 多源BFS 向外扩张，扩张时只能走海洋格子（0）。每次扩张一步，就相当于将一个海洋格子变为临时陆地（但这里我们只是计算距离）。 当BFS第一次遇到另一个岛屿（格子值为1且未被标记为2）时，此时BFS的层数就是需要翻转的海洋格子数目。因为BFS是按层扩散，第一次遇到目标时的路径是最短的。 第三步：详细步骤分解 步骤1：用DFS标记第一座岛屿 遍历矩阵，找到第一个值为1的格子，就从这个格子开始进行DFS（或BFS），将连通的所有1标记为2（表示第一座岛屿）。 DFS过程中，记录下所有属于该岛屿的格子坐标，这些坐标将作为多源BFS的起始点队列。 步骤2：多源BFS找最短距离 初始化一个队列，将第一座岛屿的所有格子的坐标加入队列，并将它们的距离设为0（因为从岛屿本身出发，不需要翻转）。 开始BFS循环： 从队列中取出一个格子，检查其四个方向（上、下、左、右）。 如果相邻格子是海洋（值为0），则将其标记为已访问（例如标记为2，或使用单独的访问数组），并将它的距离设为当前距离+1，然后加入队列。 如果相邻格子是陆地（值为1）且未被标记为2（即属于第二座岛屿），则说明我们找到了另一座岛屿。此时当前距离就是需要翻转的海洋格子数，因为BFS的层数就是已翻转的格子数。 由于BFS是逐层扩散，第一次遇到第二座岛屿时，当前的层数（距离）就是最短的。 第四步：示例推演 以示例2为例： grid = [ [ 0,1,0],[ 0,0,0],[ 0,0,1] ] 找到第一个1在(0,1)，DFS标记第一座岛屿：只有(0,1)一个格子，标记为2。 多源BFS起点队列：[ (0,1) ]，距离0。 第一步扩散：从(0,1)可走到(0,0)和(0,2)（都是0），标记它们距离为1，加入队列。 第二步扩散：从(0,0)可走到(1,0)（距离2）；从(0,2)可走到(1,2)（距离2）。加入队列。 第三步扩散：从(1,0)可走到(2,0)（距离3）；从(1,2)可走到(2,2)（但(2,2)是1，且不是2，即第二座岛屿）。此时发现第二座岛屿，当前距离是2（因为从(1,2)到(2,2)时，BFS层数是2）。 所以答案是2。 第五步：关键注意点 标记第一座岛屿时，要用DFS/BFS遍历所有连通的1，不要漏掉。 多源BFS必须从第一座岛屿的所有边界同时开始，才能保证找到最短路径。 在BFS中，遇到海洋（0）就继续扩散并记录距离；遇到未标记的1（即第二座岛屿）就立即返回当前距离。 由于n最大100，BFS时间复杂度O(n²)是可行的。 第六步：算法复杂度 时间：O(n²)，每个格子最多被访问两次（标记岛屿一次，BFS一次）。 空间：O(n²)，用于队列和标记数组。 这个解法巧妙地结合了DFS标记和BFS最短路径搜索，是解决“最短的桥”问题的标准方法。