搜索题目：最短的桥

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题最短的桥出处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}ngrid.lengthgrid[i].length2 ≤ n ≤ 100 \texttt{2} \le \texttt{n} \le \texttt{100}2≤n≤100grid[i][j] \texttt{grid[i][j]}grid[i][j]为0 \texttt{0}0或1 \texttt{1}1grid \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.ngrid.length;this.gridgrid;inttotaln*n;intstartRow-1,startCol-1;for(inti0;itotal;i){introwi/n,coli%n;if(grid[row][col]1){startRowrow;startColcol;break;}}Listint[]islandgetIsland(startRow,startCol);boolean[][]visitednewboolean[n][n];Queueint[]queuenewArrayDequeint[]();for(int[]cell:island){introwcell[0],colcell[1];visited[row][col]true;queue.offer(cell);}intdistance-1;while(!queue.isEmpty()){distance;intsizequeue.size();for(inti0;isize;i){int[]cellqueue.poll();introwcell[0],colcell[1];for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRownnewCol0newColn!visited[newRow][newCol]){if(grid[newRow][newCol]0){visited[newRow][newCol]true;queue.offer(newint[]{newRow,newCol});}else{returndistance;}}}}}return-1;}publicListint[]getIsland(intstartRow,intstartCol){Listint[]islandnewArrayListint[]();boolean[][]visitednewboolean[n][n];visited[startRow][startCol]true;Queueint[]queuenewArrayDequeint[]();queue.offer(newint[]{startRow,startCol});while(!queue.isEmpty()){int[]cellqueue.poll();island.add(cell);introwcell[0],colcell[1];for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRownnewCol0newColngrid[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)的空间。