本文转载自微信公众号“labuladong”，作者labuladong转载请联系labuladong公众号。孤岛问题是一道经典的高频面试题。虽然基本的岛题不难，但是岛题还有一些有趣的扩展，比如求岛的个数，求不同形状的岛的个数等等，本文将解决所有这些问题。.岛列问题的核心考点是利用DFS/BFS算法遍历二维数组。这篇文章主要讲解如何使用DFS算法来解决岛列问题，但是使用BFS算法的核心思想是完全一样的，无非就是将DFS改写成BFS。那么如何在二维矩阵中使用DFS搜索呢？如果把二维矩阵中的每个位置都看成一个节点，而这个节点的四个位置又是相邻的节点，那么整个矩阵就可以抽象成一个网状的“图”结构。根据学习数据结构和算法的框架思想，二维矩阵的DFS代码框架可以按照二叉树遍历框架改写：//二叉树遍历框架voidtraverse(TreeNoderoot){traverse(root.left);traverse(root.right);}//二维矩阵遍历框架voiddfs(int[][]grid,inti,intj,boolean[]visited){intm=grid.length,n=grid[0].length;if(i<0||j<0||i>=m||j>=n){//超出索引边界返回;}if(visited[i][j]){//遍历(i,j)return;}//进入节点(i,j)visited[i][j]=true;dfs(grid,i-1,j);//向上dfs(grid,i+1,j);//向下dfs(grid,i,j-1);//向左dfs(grid,i,j+1);//对//离开节点(i,j)visited[i][j]=false;}因为二维矩阵本质上是一张“图片”，所以需要一个visited布尔数组以防止在遍历过程中返回。如果你能看懂上面的代码，解决所有孤岛问题就很简单了。这是处理二维数组的一个额外的常用技巧。有时候你可能会看到使用“方向数组”来处理上下左右遍历，这和上图中的框架遍历代码非常相似：//方向数组分别代表上下，左,对int[][]dirs=newint[][]{{-1,0},{1,0},{0,-1},{0,1}};voiddfs(int[][]grid,inti,intj,boolean[]visited){intm=grid.length,n=grid[0].length;if(i<0||j<0||i>=m||j>=n){//超出索引边界return;}if(visited[i][j]){//已经遍历(i,j)return;}//进入节点(i,j)visited[i][j]=true;//递归遍历上下左右节点for(int[]d:dirs){intnext_i=i+d[0];intnext_j=j+d[1];dfs(grid,next_i,next_j);}//离开节点(i,j)visited[i][j]=false;}这种写法无非是用for循环来处理上下左右的遍历.您可以根据个人喜好选择书写方式。岛屿的数量这是第200题“岛屿的数量”，最简单最经典的岛屿问题。题目会输入一个二维数组格子，里面只包含0或者1，0代表海水，1代表陆地，假设矩阵四面都是海水。我们说相连的陆地形成岛屿，那么请写一个算法来计算这个矩阵网格中岛屿的数量。函数签名如下：intnumIslands(char[][]grid);比如题目给你下面的网格有四个岛，算法应该返回4：思路很简单，关键是如何找到并标记“岛”，这就需要DFS算法发挥作用，直接看解法代码：//main函数，计算岛屿个数intnumIslands(char[][]grid){intres=0;intm=grid.length,n=grid[0].length;//遍历gridfor(inti=0;i=m||j>=n){//超出索引边界返回;}if(grid[i][j]=='0'){//已经是海水返回;}//将(i,j)变成海水网格[i][j]='0';//淹没陆地dfs(grid,i+1,j);dfs(grid,i,j+1);dfs(grid,i-1,j);dfs(grid,i,j-1);}为什么每次你遇到孤岛，你非要用DFS算法“淹没”这个孤岛吗？主要是为了省事，避免维护visited数组。因为dfs函数遍历到值为0的位置，会直接返回，所以只要把所有经过的位置都设置为0，就可以起到不回头的作用。PS：这类DFS算法还有一个别名叫FloodFill算法。现在，大家觉得FloodFill这个名字是不是挺合适的呢~这是最基本的孤岛问题。看看下面的题目有什么技巧。封闭岛屿的个数上一题说了二维矩阵可以认为是被海水包围了，所以边上的陆地也算作一个岛屿。1254题“封闭岛屿数量统计”与上一题有两点不同：1、用0代表陆地，用1代表海水。2.允许您计算“封闭岛屿”的数量。所谓“闭岛”，就是一个上、下、左、右都被1包围的0，也就是说，边上的土地不算“闭岛”。函数签名如下：intclosedIsland(int[][]grid)比如题目给你下面的二维矩阵：算法返回2，只有图中灰色部分的0是一个“闭合”被海水包围的岛屿”。那么如何判断“闭岛”呢？其实很简单。如果把上一题靠边的岛屿排除掉，剩下的不就是“闭岛”吗？有了这个思路，可以直接看代码，注意这道题规定0表示陆地，1表示海水：//主要功能：计算封闭岛屿的个数intclosedIsland(int[][]grid){intm=grid.length,n=grid[0].length;for(intj=0;j=m||j>=n){return;}if(grid[i][j]==1){//已经是海水回流;}//把(i,j)变成海水grid[i][j]=1;//上下淹没左右陆地dfs(grid,i+1,j);dfs(grid,i,j+1);dfs(grid,i-1,j);dfs(grid,i,j-1);}就在前面淹没所有侧着陆，然后计算封闭岛。PS：除了DFS/BFS算法处理这类孤岛问题外，UnionFind算法也是一个可选的方法。前面的UnionFind算法是用来解决与UnionFind算法类似的问题的。这个孤岛问题的解决方案可以通过对问题1020“NumberofEnclaves”稍作修改来解决。这道题不是让你求封闭岛的个数，而是求封闭岛的面积之和。其实思路是一样的，先把边上的地淹掉，然后再清点剩下的地。注意问题1020中，1代表陆地，0代表海水：intnumEnclaves(int[][]grid){intm=grid.length,n=grid[0].length;//淹没边地for(inti=0;i=m||j>=n){//超出索引边界return0;}if(grid[i][j]==0){//已经是海水return0;}//转(i,j)进入海水网格[i][j]=0;returndfs(grid,i+1,j)+dfs(grid,i,j+1)+dfs(grid,i-1,j)+dfs(grid,i,j-1)+1;}解法和上一个类似，就不多说了。接下来的两个岛屿问题更具技术性，所以让我们关注它们。子岛的个数如果前面的题都是模板题，那你可能要开动脑筋了第1905题《子岛的统计》：这道题的关键是如何快速确定子岛？肯定可以使用UnionFind和搜索算法来判断，但是本文的重点是DFS算法，所以搜索算法就不展开了。在什么情况下，grid2中的岛B是grid1中岛A的子岛？当B岛的所有陆地也是A岛的陆地时，B岛就是A岛的子岛。反之，如果B岛有一块陆地，A岛对应的位置是海水，那么B岛就是A岛的子岛。B不是A岛的子岛。那么，我们只需要遍历grid2中的所有岛屿，排除那些不能成为子岛的岛屿，剩下的就是子岛了。按照这个思路，可以直接写成如下代码：intcountSubIslands(int[][]grid1,int[][]grid2){intm=grid1.length,n=grid1[0].length;for(inti=0;i=m||j>=n){return;}if(grid[i][j]==0){return;}grid[i][j]=0;dfs(grid,i+1,j);dfs(grid,i,j+1);dfs(grid,i-1,j);dfs(grid,i,j-1);}这道题的思路和计算“封闭岛屿”数量的思路有些相似，只是后者排除了那些靠边的岛屿，前者排除了那些不能靠边的岛屿子岛。不同岛屿的数量这是本文的最后一个岛屿主题。作为压轴戏，当然是最有趣的了。查看第694题“不同岛屿的数量”。题目还是输入一个二维矩阵，0表示海水，1表示陆地，这次让你计算distinct（不同）岛屿的个数，函数签名如下：intnumDistinctIslands(int[][]grid)比如标题输入如下二维矩阵：里面有四个岛，但是左下角和右上角的岛形状一样，所以有三个不同的岛，算法返回3、很明显，我们得想办法把二维矩阵中的“岛屿”转成字符串等类型，然后用HashSet等数据结构去重，最后得到不同岛屿的个数.如果要把岛转成字符串，就是序列化，序列化就是遍历。上一篇二叉树的序列化和反序列化讲到了二叉树和字符串之间的转换，这里类似。首先，对于形状相同的岛屿，如果从相同的起点出发，则dfs函数的遍历顺序必须相同。因为遍历顺序是硬编码在你的递归函数里的，不会动态变化的：voiddfs(int[][]grid,inti,intj){//递归顺序：dfs(grid,i-1,j);//Upperdfs(grid,i+1,j);//Downdfs(grid,i,j-1);//Leftdfs(grid,i,j+1);//Right}所以，遍历顺序从某种意义上说，可以用来描述岛的形状，比如下图中的两个岛：假设它们的遍历顺序是：下、右、上、上撤、右撤、下撤如果我用1、2、3、4代表上、下、左、右，用-1、-2、-3、-4代表上、下、左、右undo，就可以表达它们的遍历顺序像这样：2,4,1,-1,-4,-2你看，这相当于孤岛序列化的结果。只要每次用dfs遍历岛屿的时候生成这串数字进行比较，就可以算出有多少个不同的岛屿。要生成这个数字，需要稍微修改dfs函数，增加一些函数参数来记录遍历顺序：voiddfs(int[][]grid,inti,intj,StringBuildersb,intdir){intm=grid.length,n=grid[0].length;if(i<0||j<0||i>=m||j>=n||grid[i][j]==0){return;}//前序遍历position:enter(i,j)grid[i][j]=0;sb.append(dir).append(',');dfs(grid,i-1,j,sb,1);//向上dfs(grid,i+1,j,sb,2);//向下dfs(grid,i,j-1,sb,3);//向左dfs(grid,i,j+1,sb,4);//右//后序遍历位置：leave(i,j)sb.append(-dir).append(',');}dir记录的方向，dfs函数递归结束后，sb记录的是整个遍历顺序，其实回溯算法的核心套路就是上面提到的回溯算法框架。你可以看到这些算法都是相连的。有了这个dfs函数，就很好办了，我们直接写最终求解代码即可：intnumDistinctIslands(int[][]grid){intm=grid.length,n=grid[0].length;//记录所有岛屿HashSetislands=newHashSet<>();for(inti=0;i
