leetcode200. 岛屿数量C++题解，精美图例和流程图，一题带你弄懂图的dfs遍历算法

leetcode200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1

示例 2：
输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

题意分析

这个问题是关于图的连通分量的识别。在本题中，图由一个二维矩阵表示，其中每个顶点是一个单元格，边是单元格之间的连接（上下左右）。问题的目标是找出矩阵中所有互不相连的“岛屿”数量，即有多少个连通分量。
以示例2为例子进行画图分析。可以看到结果3座岛屿是怎么来的。

问题难点分析

解决这个问题的一个主要难点在于如何有效地识别并遍历一个岛屿，同时确保不会重复计算或遗漏任何一个岛屿。此外，还需要考虑如何优雅地处理网格边缘的单元格，避免数组越界错误。

算法分析

深度优先搜索（DFS）是一种遍历图的算法，它从一个顶点开始，沿着一条路径尽可能深地搜索，直到所有顶点都被访问过。当遇到一个未访问的相邻顶点时，算法会递归地继续搜索。在本题中，DFS可以用来遍历每个岛屿，将岛屿上的所有陆地单元格标记为已访问，从而确保每个岛屿只被计数一次。

算法步骤

1.定义DFS函数：
定义一个名为dfs的递归函数，它接收当前单元格的坐标(x, y)和岛屿矩阵grid作为参数。
DFS函数内部逻辑：
（1）标记当前单元格：在grid中将当前单元格的值从’1’改为’0’，表示该单元格已经被访问过。
（2）遍历四个方向：对于当前单元格的上、下、左、右四个可能的相邻单元格，使用两个嵌套循环遍历这四个方向。如图。

（3）检查相邻单元格：对于每个方向，计算新的位置(tx, ty)，然后检查以下条件：

新位置(tx, ty)是否在矩阵的边界内（即tx和ty的值是否在合法范围内）。
grid[tx][ty]是否为’1’，即该位置是否是陆地。

（4）递归调用DFS：如果相邻单元格满足上述所有条件，则对(tx, ty)调用dfs函数，进行深度优先搜索。

2.主函数numIslands逻辑：
获取grid的行数m和列数n。
初始化岛屿计数器res为0。

3.遍历整个矩阵：
使用两个嵌套循环遍历矩阵grid中的每个单元格。外层循环遍历行，内层循环遍历列。

4.检查单元格并调用DFS：
在遍历过程中，如果发现某个单元格的值为’1’，表示这是一个岛屿的一部分，并且尚未被访问过。
对于这样的单元格，调用dfs函数，从这个单元格开始深度优先搜索整个岛屿，同时将岛屿计数器res增加1。

算法流程图

算法细节

1.在DFS函数中，我们首先将当前单元格标记为已访问，这是为了防止在搜索过程中重复访问同一个岛屿的单元格。

2.在遍历四个方向时，我们使用dx和dy数组来简化代码，这两个数组分别存储了在x和y方向上的偏移量。
这是涉及图的DFS算法遍历题中的常见手法，先定义两个大小为4的数组，分别代表{0 , 1} {0 , -1}{1 , 0}{-1 , 0}四个方向，之后在DFS遍历时候使用for循环遍历四次即可访问上下左右四个方向。

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
for(int i=0;i<4;i++)
   {
         int tx=x+dx[i];
         int ty=y+dy[i];
         ......
   }

这些代码具有普适性，完全可以直接记住！

3.在检查相邻单元格时，我们不仅要检查它是否在矩阵范围内，还要检查是否是 ‘0’ ，这里有两层含义，既可能不是陆地，也有可能是陆地但被访问过了，所以不会再被访问。这是DFS算法的关键部分，确保我们只访问岛屿一次，并且不会重复访问。

4.在主函数中，我们使用两个嵌套循环来遍历矩阵的每个单元格，这样可以确保我们检查到矩阵的每个角落。
每次调用DFS函数时，我们都会从一个新的岛屿开始搜索，因此需要增加岛屿计数器。

具体代码

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    void dfs(int x,int y,vector<vector<char>>& grid)
    {
         grid[x][y]='0';
         for(int i=0;i<4;i++)
         {
             int tx=x+dx[i];
             int ty=y+dy[i];
if(tx>=0 && tx<grid.size() && ty>=0 && ty<grid[0].size() && grid[tx][ty]=='1')
             {
                 dfs(tx,ty,grid);
             }
         }
     return ;
    }
    int numIslands(vector<vector<char>>& grid) {
    int m=grid.size();
    int n=grid[0].size();
    int res=0;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(grid[i][j]=='1') 
            {
                dfs(i,j,grid);
                res++;
            }
        }
    }
    return res;
    }
};

模拟流程

用图模拟了一下示例2的执行流程，由于我们遍历上下左右的时候是右、左、下、上（{0 , 1} {0 , -1}{1 , 0}{-1 , 0}），所以是这样的情况。不同的遍历顺序会使箭头顺序不同，但总体逻辑不变。

复杂度分析

对于本题，DFS的时间复杂度是O(mn)，其中m和n分别是网格的行数和列数。
空间复杂度主要取决于递归栈的深度，在最坏情况下也是O(mn)。

常见错误和陷阱

1.忘记标记已访问的单元格，导致重复访问。
2.在边界检查时使用错误的条件，导致数组越界。
3.在DFS递归中错误地更新岛屿计数器。

类似题

分享交流

欢迎您在评论区分享您的解题思路和代码，与我和其他编程爱好者交流心得。