搜索题目：使陆地分离的最少天数

文章目录题目标题和出处难度题目描述要求示例数据范围前言解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析题目标题和出处标题使陆地分离的最少天数出处1568. 使陆地分离的最少天数难度8 级题目描述要求给定一个m × n \texttt{m} \times \texttt{n}m×n的二进制网格grid \texttt{grid}grid其中1 \texttt{1}1代表陆地0 \texttt{0}0代表水域。岛屿是由相邻的1 \texttt{1}1在水平方向或竖直方向上连接构成的最大组合。如果恰好有一个岛屿则认为网格是连通的否则网格是分离的。一天内可以将任何单个陆地单元1 \texttt{1}1更改为水单元0 \texttt{0}0。返回使陆地分离的最少天数。示例示例 1输入grid [[0,1,1,0],[0,1,1,0],[0,0,0,0]] \texttt{grid [[0,1,1,0],[0,1,1,0],[0,0,0,0]]}grid [[0,1,1,0],[0,1,1,0],[0,0,0,0]]输出2 \texttt{2}2解释至少需要2 \texttt{2}2天得到分离的陆地。将陆地grid[1][1] \texttt{grid[1][1]}grid[1][1]和grid[0][2] \texttt{grid[0][2]}grid[0][2]更改为水得到两个分离的岛屿。示例 2输入grid [[1,1]] \texttt{grid [[1,1]]}grid [[1,1]]输出2 \texttt{2}2解释如果网格中都是水也是分离的[[1,1]] → [[0,0]] \texttt{[[1,1]]} \rightarrow \texttt{[[0,0]]}[[1,1]]→[[0,0]]。零岛屿。数据范围m grid.length \texttt{m} \texttt{grid.length}mgrid.lengthn grid[i].length \texttt{n} \texttt{grid[i].length}ngrid[i].length1 ≤ m, n ≤ 30 \texttt{1} \le \texttt{m, n} \le \texttt{30}1≤m, n≤30grid[i][j] \texttt{grid[i][j]}grid[i][j]为0 \texttt{0}0或1 \texttt{1}1前言如果初始时网格中没有岛屿或者有至少两个岛屿则陆地已经分离不需要将任何陆地单元更改为水单元最少天数是0 00。如果初始时网格中有一个或两个陆地单元组成的岛屿则需要将所有陆地单元更改为水单元最少天数等于陆地单元的数目。如果初始时网格中恰好有一个岛屿则岛屿一定存在角落岛屿角落的单元最多和两个陆地单元相连将与岛屿角落相连的陆地单元更改为水单元之后岛屿角落的单元成为独立的岛屿此时陆地分离。因此使陆地分离的最少天数不超过2 22。如果将1 11个陆地单元更改为水单元可以使陆地分离则最少天数是1 11否则最少天数是2 22。因此最少天数一定不超过2 22。问题转化成判断是否可以通过将1 11个陆地单元更改为水单元可以使陆地分离。根据上述分析计算使陆地分离的最少天数的做法如下。计算初始时网格中的岛屿数量如果初始岛屿数量不等于1 11则最少天数是0 00。如果初始岛屿数量等于1 11则遍历每个陆地单元分别计算将每个陆地单元更改为水单元之后的岛屿数量。如果存在一个陆地单元将该陆地单元更改为水单元之后的岛屿数量不等于1 11则最少天数是1 11。如果不存在这样的陆地单元则最少天数是2 22。计算岛屿数量可以使用广度优先搜索或深度优先搜索实现。解法一思路和算法使用广度优先搜索计算岛屿数量的做法是依次遍历网格中的每个单元如果遇到一个单元是陆地且状态是未访问则遇到一个新的岛屿将岛屿数量加1 11并使用广度优先搜索访问与当前陆地连接的所有陆地即访问当前岛屿的所有单元。遍历结束之后即可得到岛屿数量。如果初始岛屿数量等于1 11则依次遍历每个陆地对于每个陆地将陆地更改为水之后计算岛屿数量计算结束之后将该单元恢复成陆地继续遍历其他的陆地。代码classSolution{staticint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};intm,n;int[][]grid;publicintminDays(int[][]grid){this.mgrid.length;this.ngrid[0].length;this.gridgrid;if(numIslands()!1){return0;}for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){grid[i][j]0;if(numIslands()!1){return1;}grid[i][j]1;}}}return2;}publicintnumIslands(){intislands0;boolean[][]visitednewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]0||visited[i][j]){continue;}islands;visited[i][j]true;Queueint[]queuenewArrayDequeint[]();queue.offer(newint[]{i,j});while(!queue.isEmpty()){int[]cellqueue.poll();introwcell[0],colcell[1];for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRowmnewCol0newColngrid[newRow][newCol]1!visited[newRow][newCol]){visited[newRow][newCol]true;queue.offer(newint[]{newRow,newCol});}}}}}returnislands;}}复杂度分析时间复杂度O ( m 2 n 2 ) O(m^2n^2)O(m2n2)其中m mm和n nn分别是网格grid \textit{grid}grid的行数和列数。计算初始岛屿数量需要O ( m n ) O(mn)O(mn)的时间对于每个陆地单元更改为水单元之后计算岛屿数量需要O ( m n ) O(mn)O(mn)的时间由于陆地单元的数量是O ( m n ) O(mn)O(mn)因此对于所有陆地单元计算更改为水单元之后的岛屿数量需要O ( m 2 n 2 ) O(m^2n^2)O(m2n2)的时间总时间复杂度是O ( m n m 2 n 2 ) O ( m 2 n 2 ) O(mn m^2n^2) O(m^2n^2)O(mnm2n2)O(m2n2)。空间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是网格grid \textit{grid}grid的行数和列数。记录每个单元格是否访问过的二维数组和队列需要O ( m n ) O(mn)O(mn)的空间。解法二思路和算法使用深度优先搜索计算岛屿数量的做法是依次遍历网格中的每个单元如果遇到一个单元是陆地且状态是未访问则遇到一个新的岛屿将岛屿数量加1 11并使用深度优先搜索访问与当前陆地连接的所有陆地即访问当前岛屿的所有单元。遍历结束之后即可得到岛屿数量。如果初始岛屿数量等于1 11则依次遍历每个陆地对于每个陆地将陆地更改为水之后计算岛屿数量计算结束之后将该单元恢复成陆地继续遍历其他的陆地。代码classSolution{staticint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};intm,n;int[][]grid;boolean[][]visited;publicintminDays(int[][]grid){this.mgrid.length;this.ngrid[0].length;this.gridgrid;if(numIslands()!1){return0;}for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){grid[i][j]0;if(numIslands()!1){return1;}grid[i][j]1;}}}return2;}publicintnumIslands(){intislands0;this.visitednewboolean[m][n];for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]0||visited[i][j]){continue;}islands;dfs(i,j);}}returnislands;}publicvoiddfs(introw,intcol){visited[row][col]true;for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRowmnewCol0newColngrid[newRow][newCol]1!visited[newRow][newCol]){dfs(newRow,newCol);}}}}复杂度分析时间复杂度O ( m 2 n 2 ) O(m^2n^2)O(m2n2)其中m mm和n nn分别是网格grid \textit{grid}grid的行数和列数。计算初始岛屿数量需要O ( m n ) O(mn)O(mn)的时间对于每个陆地单元更改为水单元之后计算岛屿数量需要O ( m n ) O(mn)O(mn)的时间由于陆地单元的数量是O ( m n ) O(mn)O(mn)因此对于所有陆地单元计算更改为水单元之后的岛屿数量需要O ( m 2 n 2 ) O(m^2n^2)O(m2n2)的时间总时间复杂度是O ( m n m 2 n 2 ) O ( m 2 n 2 ) O(mn m^2n^2) O(m^2n^2)O(mnm2n2)O(m2n2)。空间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是网格grid \textit{grid}grid的行数和列数。记录每个单元格是否访问过的二维数组和递归调用栈需要O ( m n ) O(mn)O(mn)的空间。