企业官网建设流程全解析

题目

标题和出处

标题：最短的桥

出处：934. 最短的桥

难度

5 级

题目描述

要求

给定一个n × n \texttt{n} \times \texttt{n}n×n的二进制矩阵grid \texttt{grid}grid，其中1 \texttt{1}1表示陆地，0 \texttt{0}0表示水域。

岛是由四面相连的1 \texttt{1}1形成的一个最大组，即不会与非组内的任何其他1 \texttt{1}1相连。矩阵grid \texttt{grid}grid中恰好存在两个岛。

可以将任意数量的0 \texttt{0}0变为1 \texttt{1}1，使两座岛连接组成一个岛。

返回必须翻转的0 \texttt{0}0的最小数目。

示例

示例 1：

输入：grid = [[0,1],[1,0]] \texttt{grid = [[0,1],[1,0]]}grid = [[0,1],[1,0]]
输出：1 \texttt{1}1

示例 2：

输入：grid = [[0,1,0],[0,0,0],[0,0,1]] \texttt{grid = [[0,1,0],[0,0,0],[0,0,1]]}grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2 \texttt{2}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]] \texttt{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]]}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 \texttt{1}1

数据范围

• n = grid.length = grid[i].length \texttt{n} = \texttt{grid.length} = \texttt{grid[i].length}n=grid.length=grid[i].length
• 2 ≤ n ≤ 100 \texttt{2} \le \texttt{n} \le \texttt{100}2≤n≤100
• grid[i][j] \texttt{grid[i][j]}grid[i][j]为0 \texttt{0}0或1 \texttt{1}1
• grid \texttt{grid}grid中恰有两个岛

解法

思路和算法

由于一个岛由相邻的陆地连接形成，因此只要得到岛上的一个陆地，即可使用搜索的方法得到该陆地所在的岛上的所有陆地。

由于矩阵中恰有两个岛，因此可以首先遍历矩阵得到其中一个岛上的陆地，从该陆地开始搜索其所在的岛上的所有陆地，然后从已知岛开始搜索未知岛，计算两个岛之间的最短距离。

从一个陆地开始搜索其所在的岛上的所有陆地，可以使用广度优先搜索或深度优先搜索，这里使用广度优先搜索。

得到已知岛上的所有陆地之后，从已知岛上的所有陆地出发执行多源广度优先搜索，寻找未知岛，搜索过程中记录距离。

为了得到最短距离，在广度优先搜索的过程中需要将元素分组，确保每一轮遍历的元素为同一层的全部待访问元素，同一层的全部待访问元素与已知岛的最短距离相同。

初始时，将已知岛上的所有陆地入队列。每一轮遍历之前需要首先得到队列内的元素个数，此时队列内的元素为同一层的全部待访问元素，然后访问这些元素，并将与这些元素相邻且未访问的水域入队列。一轮遍历结束之后，当前层的全部元素都已经出队列并被访问，此时队列内的元素为下一层的全部待访问元素，下一轮遍历时即可访问下一层的全部待访问元素。该做法可以确保每一轮遍历的元素为同一层的全部待访问元素。

具体做法是，将距离初始化为− 1 -1−1，表示尚未访问任何元素。每一轮遍历时，将距离加1 11，然后遍历当前层的全部待访问元素，对于当前层的每个待访问元素，如果存在相邻元素是未访问的水域或陆地，执行如下操作。

• 如果相邻元素是未访问的水域，则将该水域的状态设为已访问，并入队列。

• 如果相邻元素是未访问的陆地，则该未访问的陆地属于另一个岛屿，此时的距离即为两个岛之间必须翻转的0 00的最小数目，返回距离。

由于矩阵中恰有两个岛，因此一定可以得到两个岛之间必须翻转的0 00的最小数目。

代码

classSolution{staticint[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};intn;int[][]grid;publicintshortestBridge(int[][]grid){this.n=grid.length;this.grid=grid;inttotal=n*n;intstartRow=-1,startCol=-1;for(inti=0;i<total;i++){introw=i/n,col=i%n;if(grid[row][col]==1){startRow=row;startCol=col;break;}}List<int[]>island=getIsland(startRow,startCol);boolean[][]visited=newboolean[n][n];Queue<int[]>queue=newArrayDeque<int[]>();for(int[]cell:island){introw=cell[0],col=cell[1];visited[row][col]=true;queue.offer(cell);}intdistance=-1;while(!queue.isEmpty()){distance++;intsize=queue.size();for(inti=0;i<size;i++){int[]cell=queue.poll();introw=cell[0],col=cell[1];for(int[]dir:dirs){intnewRow=row+dir[0],newCol=col+dir[1];if(newRow>=0&&newRow<n&&newCol>=0&&newCol<n&&!visited[newRow][newCol]){if(grid[newRow][newCol]==0){visited[newRow][newCol]=true;queue.offer(newint[]{newRow,newCol});}else{returndistance;}}}}}return-1;}publicList<int[]>getIsland(intstartRow,intstartCol){List<int[]>island=newArrayList<int[]>();boolean[][]visited=newboolean[n][n];visited[startRow][startCol]=true;Queue<int[]>queue=newArrayDeque<int[]>();queue.offer(newint[]{startRow,startCol});while(!queue.isEmpty()){int[]cell=queue.poll();island.add(cell);introw=cell[0],col=cell[1];for(int[]dir:dirs){intnewRow=row+dir[0],newCol=col+dir[1];if(newRow>=0&&newRow<n&&newCol>=0&&newCol<n&&grid[newRow][newCol]==1&&!visited[newRow][newCol]){visited[newRow][newCol]=true;queue.offer(newint[]{newRow,newCol});}}}returnisland;}}

复杂度分析

• 时间复杂度：O ( n 2 ) O(n^2)O(n2)，其中n nn是矩阵grid \textit{grid}grid的边长。遍历和搜索一个岛需要O ( n 2 ) O(n^2)O(n2)的时间，搜索两个岛之间的最短距离也需要O ( n 2 ) O(n^2)O(n2)的时间。

• 空间复杂度：O ( n 2 ) O(n^2)O(n2)，其中n nn是矩阵grid \textit{grid}grid的边长。使用列表记录一个岛的全部陆地需要O ( n 2 ) O(n^2)O(n2)的空间，广度优先搜索使用的队列需要O ( n 2 ) O(n^2)O(n2)的空间。