dfs算法迷宫（dfs算法详解）

岛屿问题是经典的面试高频题，虽然基本的岛屿问题并不难，但是岛屿问题有一些有意思的扩展，比如求子岛屿数量，求形状不同的岛屿数量等等，本文就来把这些问题一网打尽。

岛屿系列问题的核心考点就是用 DFS/BFS 算法遍历二维数组。

本文主要来讲解如何用 DFS 算法来秒杀岛屿系列问题，不过用 BFS 算法的核心思路是完全一样的，无非就是把 DFS 改写成 BFS 而已。

那么如何在二维矩阵中使用 DFS 搜索呢?如果你把二维矩阵中的每一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构。

根据 学习数据结构和算法的框架思维，完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架：

1. //二叉树遍历框架
2. voidtraverse(TreeNoderoot){
3. traverse(root.left);
4. traverse(root.right);
5. }
7. //二维矩阵遍历框架
8. voiddfs(int[][]grid,inti,intj,boolean[]visited){
9. intm=grid.length,n=grid[0].length;
10. if(i<0||j<0||i>=m||j>=n){
11. //超出索引边界
12. return;
13. }
14. if(visited[i][j]){
15. //已遍历过(i,j)
16. return;
17. }
18. //进入节点(i,j)
19. visited[i][j]=true;
20. dfs(grid,i-1,j);//上
21. dfs(grid,i+1,j);//下
22. dfs(grid,i,j-1);//左
23. dfs(grid,i,j+1);//右
24. //离开节点(i,j)
25. visited[i][j]=false;
26. }

因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个visited布尔数组防止走回头路，如果你能理解上面这段代码，那么搞定所有岛屿问题都很简单。

这里额外说一个处理二维数组的常用小技巧，你有时会看到使用「方向数组」来处理上下左右的遍历，和前文 图遍历框架 的代码很类似：

1. //方向数组，分别代表上、下、左、右
2. int[][]dirs=newint[][]{{-1,0},{1,0},{0,-1},{0,1}};
4. voiddfs(int[][]grid,inti,intj,boolean[]visited){
5. intm=grid.length,n=grid[0].length;
6. if(i<0||j<0||i>=m||j>=n){
7. //超出索引边界
8. return;
9. }
10. if(visited[i][j]){
11. //已遍历过(i,j)
12. return;
13. }
15. //进入节点(i,j)
16. visited[i][j]=true;
17. //递归遍历上下左右的节点
18. for(int[]d:dirs){
19. intnext_i=i+d[0];
20. intnext_j=j+d[1];
21. dfs(grid,next_i,next_j);
22. }
23. //离开节点(i,j)
24. visited[i][j]=false;
25. }

这种写法无非就是用 for 循环处理上下左右的遍历罢了，你可以按照个人喜好选择写法。

岛屿数量

这是力扣第 200 题「岛屿数量」，最简单也是最经典的一道岛屿问题，题目会输入一个二维数组grid，其中只包含0或者1，0代表海水，1代表陆地，且假设该矩阵四周都是被海水包围着的。

我们说连成片的陆地形成岛屿，那么请你写一个算法，计算这个矩阵grid中岛屿的个数，函数签名如下：

1. intnumIslands(char[][]grid);

比如说题目给你输入下面这个grid有四片岛屿，算法应该返回 4：

思路很简单，关键在于如何寻找并标记「岛屿」，这就要 DFS 算法发挥作用了，我们直接看解法代码：

1. //主函数，计算岛屿数量
2. intnumIslands(char[][]grid){
3. intres=0;
4. intm=grid.length,n=grid[0].length;
5. //遍历grid
6. for(inti=0;i<m;i++){
7. for(intj=0;j<n;j++){
8. if(grid[i][j]=='1'){
9. //每发现一个岛屿，岛屿数量加一
10. res++;
11. //然后使用DFS将岛屿淹了
12. dfs(grid,i,j);
13. }
14. }
15. }
16. returnres;
17. }
19. //从(i,j)开始，将与之相邻的陆地都变成海水
20. voiddfs(char[][]grid,inti,intj){
21. intm=grid.length,n=grid[0].length;
22. if(i<0||j<0||i>=m||j>=n){
23. //超出索引边界
24. return;
25. }
26. if(grid[i][j]=='0'){
27. //已经是海水了
28. return;
29. }
30. //将(i,j)变成海水
31. grid[i][j]='0';
32. //淹没上下左右的陆地
33. dfs(grid,i+1,j);
34. dfs(grid,i,j+1);
35. dfs(grid,i-1,j);
36. dfs(grid,i,j-1);
37. }

为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢?主要是为了省事，避免维护visited数组。

因为dfs函数遍历到值为0的位置会直接返回，所以只要把经过的位置都设置为0，就可以起到不走回头路的作用。

PS：这类 DFS 算法还有个别名叫做 FloodFill 算法，现在有没有觉得 FloodFill 这个名字还挺贴切的~

这个最最基本的岛屿问题就说到这，我们来看看后面的题目有什么花样。

封闭岛屿的数量

上一题说二维矩阵四周可以认为也是被海水包围的，所以靠边的陆地也算作岛屿。

力扣第 1254 题「统计封闭岛屿的数目」和上一题有两点不同：

1、用0表示陆地，用1表示海水。

2、让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被1包围的0，也就是说靠边的陆地不算作「封闭岛屿」。

函数签名如下：

1. intclosedIsland(int[][]grid)

比如题目给你输入如下这个二维矩阵：

算法返回 2，只有图中灰色部分的0是四周全都被海水包围着的「封闭岛屿」。

那么如何判断「封闭岛屿」呢?其实很简单，把上一题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗?

有了这个思路，就可以直接看代码了，注意这题规定0表示陆地，用1表示海水：

1. //主函数：计算封闭岛屿的数量
2. intclosedIsland(int[][]grid){
3. intm=grid.length,n=grid[0].length;
4. for(intj=0;j<n;j++){
5. //把靠上边的岛屿淹掉
6. dfs(grid,0,j);
7. //把靠下边的岛屿淹掉
8. dfs(grid,m-1,j);
9. }
10. for(inti=0;i<m;i++){
11. //把靠左边的岛屿淹掉
12. dfs(grid,i,0);
13. //把靠右边的岛屿淹掉
14. dfs(grid,i,n-1);
15. }
16. //遍历grid，剩下的岛屿都是封闭岛屿
17. intres=0;
18. for(inti=0;i<m;i++){
19. for(intj=0;j<n;j++){
20. if(grid[i][j]==0){
21. res++;
22. dfs(grid,i,j);
23. }
24. }
25. }
26. returnres;
27. }
29. //从(i,j)开始，将与之相邻的陆地都变成海水
30. voiddfs(int[][]grid,inti,intj){
31. intm=grid.length,n=grid[0].length;
32. if(i<0||j<0||i>=m||j>=n){
33. return;
34. }
35. if(grid[i][j]==1){
36. //已经是海水了
37. return;
38. }
39. //将(i,j)变成海水
40. grid[i][j]=1;
41. //淹没上下左右的陆地
42. dfs(grid,i+1,j);
43. dfs(grid,i,j+1);
44. dfs(grid,i-1,j);
45. dfs(grid,i,j-1);
46. }

只要提前把靠边的陆地都淹掉，然后算出来的就是封闭岛屿了。

PS：处理这类岛屿问题除了 DFS/BFS 算法之外，Union Find 并查集算法也是一种可选的方法，前文 Union Find 算法运用 就用 Union Find 算法解决了一道类似的问题。

这道岛屿题目的解法稍微改改就可以解决力扣第 1020 题「飞地的数量」，这题不让你求封闭岛屿的数量，而是求封闭岛屿的面积总和。

其实思路都是一样的，先把靠边的陆地淹掉，然后去数剩下的陆地数量就行了，注意第 1020 题中1代表陆地，0代表海水：

1. intnumEnclaves(int[][]grid){
2. intm=grid.length,n=grid[0].length;
3. //淹掉靠边的陆地
4. for(inti=0;i<m;i++){
5. dfs(grid,i,0);
6. dfs(grid,i,n-1);
7. }
8. for(intj=0;j<n;j++){
9. dfs(grid,0,j);
10. dfs(grid,m-1,j);
11. }
13. //数一数剩下的陆地
14. intres=0;
15. for(inti=0;i<m;i++){
16. for(intj=0;j<n;j++){
17. if(grid[i][j]==1){
18. res+=1;
19. }
20. }
21. }
23. returnres;
24. }
26. //和之前的实现类似
27. voiddfs(int[][]grid,inti,intj){
28. //...
29. }

篇幅所限，具体代码我就不写了，我们继续看其他的岛屿问题。

岛屿的最大面积

这是力扣第 695 题「岛屿的最大面积」，0表示海水，1表示陆地，现在不让你计算岛屿的个数了，而是让你计算最大的那个岛屿的面积，函数签名如下：

1. intmaxAreaOfIsland(int[][]grid)

比如题目给你输入如下一个二维矩阵：

其中面积最大的是橘红色的岛屿，算法返回它的面积 6。

这题的大体思路和之前完全一样，只不过dfs函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。

我们可以给dfs函数设置返回值，记录每次淹没的陆地的个数，直接看解法吧：

1. intmaxAreaOfIsland(int[][]grid){
2. //记录岛屿的最大面积
3. intres=0;
4. intm=grid.length,n=grid[0].length;
5. for(inti=0;i<m;i++){
6. for(intj=0;j<n;j++){
7. if(grid[i][j]==1){
8. //淹没岛屿，并更新最大岛屿面积
9. res=Math.max(res,dfs(grid,i,j));
10. }
11. }
12. }
13. returnres;
14. }
16. //淹没与(i,j)相邻的陆地，并返回淹没的陆地面积
17. intdfs(int[][]grid,inti,intj){
18. intm=grid.length,n=grid[0].length;
19. if(i<0||j<0||i>=m||j>=n){
20. //超出索引边界
21. return0;
22. }
23. if(grid[i][j]==0){
24. //已经是海水了
25. return0;
26. }
27. //将(i,j)变成海水
28. grid[i][j]=0;
30. returndfs(grid,i+1,j)
31. +dfs(grid,i,j+1)
32. +dfs(grid,i-1,j)
33. +dfs(grid,i,j-1)+1;
34. }

解法和之前相比差不多，我也不多说了，接下来的两道岛屿问题是比较有技巧性的，我们重点来看一下。

子岛屿数量

如果说前面的题目都是模板题，那么力扣第 1905 题「统计子岛屿」可能得动动脑子了：

这道题的关键在于，如何快速判断子岛屿?肯定可以借助 Union Find 并查集算法 来判断，不过本文重点在 DFS 算法，就不展开并查集算法了。

什么情况下grid2中的一个岛屿B是grid1中的一个岛屿A的子岛?

当岛屿B中所有陆地在岛屿A中也是陆地的时候，岛屿B是岛屿A的子岛。

反过来说，如果岛屿B中存在一片陆地，在岛屿A的对应位置是海水，那么岛屿B就不是岛屿A的子岛。

那么，我们只要遍历grid2中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。

依据这个思路，可以直接写出下面的代码：

1. intcountSubIslands(int[][]grid1,int[][]grid2){
2. intm=grid1.length,n=grid1[0].length;
3. for(inti=0;i<m;i++){
4. for(intj=0;j<n;j++){
5. if(grid1[i][j]==0&&grid2[i][j]==1){
6. //这个岛屿肯定不是子岛，淹掉
7. dfs(grid2,i,j);
8. }
9. }
10. }
11. //现在grid2中剩下的岛屿都是子岛，计算岛屿数量
12. intres=0;
13. for(inti=0;i<m;i++){
14. for(intj=0;j<n;j++){
15. if(grid2[i][j]==1){
16. res++;
17. dfs(grid2,i,j);
18. }
19. }
20. }
21. returnres;
22. }
24. //从(i,j)开始，将与之相邻的陆地都变成海水
25. voiddfs(int[][]grid,inti,intj){
26. intm=grid.length,n=grid[0].length;
27. if(i<0||j<0||i>=m||j>=n){
28. return;
29. }
30. if(grid[i][j]==0){
31. return;
32. }
34. grid[i][j]=0;
35. dfs(grid,i+1,j);
36. dfs(grid,i,j+1);
37. dfs(grid,i-1,j);
38. dfs(grid,i,j-1);
39. }

这道题的思路和计算「封闭岛屿」数量的思路有些类似，只不过后者排除那些靠边的岛屿，前者排除那些不可能是子岛的岛屿。

不同的岛屿数量

这是本文的最后一道岛屿题目，作为压轴题，当然是最有意思的。

力扣第 694 题「不同的岛屿数量」，题目还是输入一个二维矩阵，0表示海水，1表示陆地，这次让你计算 不同的 (distinct) 岛屿数量，函数签名如下：

1. intnumDistinctIslands(int[][]grid)

比如题目输入下面这个二维矩阵：

其中有四个岛屿，但是左下角和右上角的岛屿形状相同，所以不同的岛屿共有三个，算法返回 3。

很显然我们得想办法把二维矩阵中的「岛屿」进行转化，变成比如字符串这样的类型，然后利用 HashSet 这样的数据结构去重，最终得到不同的岛屿的个数。

如果想把岛屿转化成字符串，说白了就是序列化，序列化说白了遍历嘛，前文 二叉树的序列化和反序列化 讲了二叉树和字符串互转，这里也是类似的。

首先，对于形状相同的岛屿，如果从同一起点出发，dfs函数遍历的顺序肯定是一样的。

因为遍历顺序是写死在你的递归函数里面的，不会动态改变：

1. voiddfs(int[][]grid,inti,intj){
2. //递归顺序：
3. dfs(grid,i-1,j);//上
4. dfs(grid,i+1,j);//下
5. dfs(grid,i,j-1);//左
6. dfs(grid,i,j+1);//右
7. }

所以，遍历顺序从某种意义上说就可以用来描述岛屿的形状，比如下图这两个岛屿：

假设它们的遍历顺序是：

下，右，上，撤销上，撤销右，撤销下

如果我用分别用1, 2, 3, 4代表上下左右，用-1, -2, -3, -4代表上下左右的撤销，那么可以这样表示它们的遍历顺序：

2, 4, 1, -1, -4, -2

你看，这就相当于是岛屿序列化的结果，只要每次使用dfs遍历岛屿的时候生成这串数字进行比较，就可以计算到底有多少个不同的岛屿了。

要想生成这段数字，需要稍微改造dfs函数，添加一些函数参数以便记录遍历顺序：

1. voiddfs(int[][]grid,inti,intj,StringBuildersb,intdir){
2. intm=grid.length,n=grid[0].length;
3. if(i<0||j<0||i>=m||j>=n
4. ||grid[i][j]==0){
5. return;
6. }
7. //前序遍历位置：进入(i,j)
8. grid[i][j]=0;
9. sb.append(dir).append(',');
11. dfs(grid,i-1,j,sb,1);//上
12. dfs(grid,i+1,j,sb,2);//下
13. dfs(grid,i,j-1,sb,3);//左
14. dfs(grid,i,j+1,sb,4);//右
16. //后序遍历位置：离开(i,j)
17. sb.append(-dir).append(',');
18. }

dir记录方向，dfs函数递归结束后，sb记录着整个遍历顺序，其实这就是前文 回溯算法核心套路 说到的回溯算法框架，你看到头来这些算法都是相通的。

有了这个dfs函数就好办了，我们可以直接写出最后的解法代码：

1. intnumDistinctIslands(int[][]grid){
2. intm=grid.length,n=grid[0].length;
3. //记录所有岛屿的序列化结果
4. HashSet<String>islands=newHashSet<>();
5. for(inti=0;i<m;i++){
6. for(intj=0;j<n;j++){
7. if(grid[i][j]==1){
8. //淹掉这个岛屿，同时存储岛屿的序列化结果
9. StringBuildersb=newStringBuilder();
10. //初始的方向可以随便写，不影响正确性
11. dfs(grid,i,j,sb,666);
12. islands.add(sb.toString());
13. }
14. }
15. }
16. //不相同的岛屿数量
17. returnislands.size();
18. }

这样，这道题就解决了，至于为什么初始调用dfs函数时的dir参数可以随意写，这里涉及 DFS 和回溯算法的一个细微差别，前文 图算法基础 有写，这里就不展开了。

以上就是全部岛屿系列问题的解题思路，也许前面的题目大部分人会做，但是最后两题还是比较巧妙的，希望本文对你有帮助。

原文链接：https://mp.weixin.qq.com/s/IZQkb-M27dt-AZ1VICThOw