算法题最短的桥-洪萨配资

934. 最短的桥

问题描述

给你一个大小为n x n的二进制矩阵grid，其中1表示陆地，0表示水域。

保证恰好有两座岛（即两个由1组成的连通分量）。

你可以将0变成1来建造桥梁，使得两座岛连接起来。

返回需要建造的最短桥梁的长度（即最少需要翻转多少个0）。

注意：在二维网格中，连通性是指上下左右四个方向。

示例：

输入: grid = [[0,1],[1,0]] 输出: 1 解释: 翻转 grid[0][0] 或 grid[1][1] 即可连接两座岛。 输入: grid = [[0,1,0],[0,0,0],[0,0,1]] 输出: 2 解释: 翻转 grid[0][2] 和 grid[1][2]，或者翻转 grid[1][0] 和 grid[2][0]。 输入: 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 解释: 中间的0只需要翻转一个即可连接。

算法思路

多源BFS：

步骤：

找到第一座岛：使用DFS或BFS遍历找到其中一个连通分量（岛）
标记第一座岛：将第一座岛的所有位置标记为特殊值（如2），并将所有边界位置加入BFS队列
多源BFS扩展：从第一座岛的所有位置同时开始BFS，寻找第二座岛
返回距离：当BFS第一次遇到值为1的位置时，当前的BFS层数就是最短桥梁长度

代码实现

方法一：DFS + 多源BFS

classSolution{privatestaticfinalint[][]DIRECTIONS={{-1,0},{1,0},{0,-1},{0,1}};/** * 找到连接两座岛的最短桥梁长度 * * @param grid n x n 的二进制矩阵 * @return 最短桥梁长度 */publicintshortestBridge(int[][]grid){intn=grid.length;booleanfoundFirstIsland=false;Queue<int[]>queue=newLinkedList<>();// 1: 找到第一座岛并标记for(inti=0;i<n&&!foundFirstIsland;i++){for(intj=0;j<n&&!foundFirstIsland;j++){if(grid[i][j]==1){// 使用DFS标记第一座岛为2，并将所有位置加入BFS队列dfsMarkIsland(grid,i,j,queue);foundFirstIsland=true;}}}// 2: 多源BFS寻找第二座岛intbridgeLength=0;while(!queue.isEmpty()){intsize=queue.size();// 处理当前BFS层的所有节点for(inti=0;i<size;i++){int[]current=queue.poll();introw=current[0];intcol=current[1];// 探索四个方向for(int[]dir:DIRECTIONS){intnewRow=row+dir[0];intnewCol=col+dir[1];// 边界检查if(newRow>=0&&newRow<n&&newCol>=0&&newCol<n){if(grid[newRow][newCol]==1){// 找到第二座岛，返回当前桥梁长度returnbridgeLength;}elseif(grid[newRow][newCol]==0){// 水域，标记为已访问并加入队列grid[newRow][newCol]=2;queue.offer(newint[]{newRow,newCol});}// 如果是2（第一座岛），跳过}}}bridgeLength++;}return-1;//}/** * DFS标记第一座岛为2，并将所有位置加入BFS队列 */privatevoiddfsMarkIsland(int[][]grid,introw,intcol,Queue<int[]>queue){intn=grid.length;// 边界检查和访问检查if(row<0||row>=n||col<0||col>=n||grid[row][col]!=1){return;}// 标记为第一座岛（2）并加入BFS队列grid[row][col]=2;queue.offer(newint[]{row,col});// 递归标记相邻的陆地for(int[]dir:DIRECTIONS){dfsMarkIsland(grid,row+dir[0],col+dir[1],queue);}}}

方法二：BFS + 多源BFS

classSolution{privatestaticfinalint[][]DIRECTIONS={{-1,0},{1,0},{0,-1},{0,1}};publicintshortestBridge(int[][]grid){intn=grid.length;Queue<int[]>queue=newLinkedList<>();booleanfoundFirstIsland=false;// 使用BFS找到并标记第一座岛for(inti=0;i<n&&!foundFirstIsland;i++){for(intj=0;j<n&&!foundFirstIsland;j++){if(grid[i][j]==1){bfsMarkIsland(grid,i,j,queue);foundFirstIsland=true;}}}// 多源BFSreturnmultiSourceBFS(grid,queue);}privatevoidbfsMarkIsland(int[][]grid,intstartRow,intstartCol,Queue<int[]>queue){intn=grid.length;Queue<int[]>islandQueue=newLinkedList<>();islandQueue.offer(newint[]{startRow,startCol});grid[startRow][startCol]=2;queue.offer(newint[]{startRow,startCol});while(!islandQueue.isEmpty()){int[]current=islandQueue.poll();introw=current[0];intcol=current[1];for(int[]dir:DIRECTIONS){intnewRow=row+dir[0];intnewCol=col+dir[1];if(newRow>=0&&newRow<n&&newCol>=0&&newCol<n&&grid[newRow][newCol]==1){grid[newRow][newCol]=2;islandQueue.offer(newint[]{newRow,newCol});queue.offer(newint[]{newRow,newCol});}}}}privateintmultiSourceBFS(int[][]grid,Queue<int[]>queue){intn=grid.length;intbridgeLength=0;while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){int[]current=queue.poll();introw=current[0];intcol=current[1];for(int[]dir:DIRECTIONS){intnewRow=row+dir[0];intnewCol=col+dir[1];if(newRow>=0&&newRow<n&&newCol>=0&&newCol<n){if(grid[newRow][newCol]==1){returnbridgeLength;}elseif(grid[newRow][newCol]==0){grid[newRow][newCol]=2;queue.offer(newint[]{newRow,newCol});}}}}bridgeLength++;}return-1;}}

算法分析

时间复杂度：O(n²)
- DFS/BFS标记第一座岛：O(n²)
- 多源BFS扩展：O(n²)
空间复杂度：O(n²)
- 队列在最坏情况下可能存储O(n²)个元素
- 递归DFS的栈深度最坏情况下也是O(n²)

算法过程

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

找到第一座岛：
- 在(0,1)找到第一个1
- DFS标记第一座岛：只有(0,1)，标记为2
- BFS队列：[(0,1)]
多源BFS：
- 层0：队列[(0,1)]
- 探索邻居：(0,0)=0→标记为2加入队列，(1,1)=0→标记为2加入队列，(0,2)和(-1,1)越界
- 层1：队列[(0,0), (1,1)]
- 从(1,1)探索(1,0)=1→找到第二座岛！
- 返回桥梁长度 = 1

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

标记第一座岛：(0,1)标记为2，队列[(0,1)]
BFS层0：探索(0,0)=0、(0,2)=0、(1,1)=0 → 队列[(0,0),(0,2),(1,1)]
BFS层1：从(0,2)探索(1,2)=0；从(1,1)探索(1,0)=0、(1,2)=0、(2,1)=0 → 队列包含这些位置
BFS层2：从(1,2)探索(2,2)=1 → 找到第二座岛，返回2

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：最小情况int[][]grid1={{0,1},{1,0}};System.out.println("Test 1: "+solution.shortestBridge(grid1));// 1// 测试用例2：标准示例int[][]grid2={{0,1,0},{0,0,0},{0,0,1}};System.out.println("Test 2: "+solution.shortestBridge(grid2));// 2// 测试用例3：环形岛屿int[][]grid3={{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}};System.out.println("Test 3: "+solution.shortestBridge(grid3));// 1// 测试用例4：大岛屿int[][]grid4={{1,1,0,0,0},{1,0,0,0,0},{0,0,0,0,1},{0,0,0,1,1},{0,0,0,1,1}};System.out.println("Test 4: "+solution.shortestBridge(grid4));// 3// 测试用例5：相邻岛屿int[][]grid5={{1,0,1},{0,0,0},{0,0,0}};System.out.println("Test 5: "+solution.shortestBridge(grid5));// 1// 测试用例6：单格岛屿int[][]grid6={{1,0,0},{0,0,0},{0,0,1}};System.out.println("Test 6: "+solution.shortestBridge(grid6));// 3// 测试用例7：复杂形状int[][]grid7={{0,0,0,0,0,0},{0,1,1,0,0,0},{0,1,0,0,0,0},{0,0,0,0,1,0},{0,0,0,1,1,0},{0,0,0,0,0,0}};System.out.println("Test 7: "+solution.shortestBridge(grid7));// 2}