【Hot 100 刷题计划】 LeetCode 200. 岛屿数量 | C++ DFS 题解

LeetCode 200. 岛屿数量 | C DFS Flood Fill 题解 题目描述题目级别中等给你一个由1陆地和0水组成的的二维网格grid请你计算网格中岛屿的数量。岛屿定义岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。假设你可以假设该网格的四条边均被水包围。 解题思路深度优先搜索 (DFS) Flood Fill 算法这道题是经典的连通块问题我们可以把二维网格看作一个图。核心本质Flood Fill洪水灌溉想象一下每一个1陆地都是干柴而0水是防火带。我们的目标是数数一共燃起了几把不相连的火。寻找火种我们遍历整个网格。当我们遇到一个是陆地 (1) 且没有被访问过的格子时这就意味着我们找到了一个新的岛屿起点。我们将岛屿计数res。星星之火可以燎原 (DFS)从这个起点开始我们立刻发动 DFS深度优先搜索。DFS 会像火焰或者洪水一样迅速向上下左右四个方向蔓延将所有相邻且相连的陆地全部标记为“已访问”。熄灭火标记访问在代码中我们使用一个二维数组st[350][350]来记录哪些格子已经被标记过。继续寻找DFS 蔓延结束后回到主循环。我们继续向后遍历。由于刚才 DFS 的功劳那一整座岛屿的陆地都已经被标记为“已访问”我们在遍历时会自动跳过它们。直到遇到下一个没有被访问过的1这又是另一座新岛屿的开始了。细节处理方向数组使用int dx[4] {0, 1, 0, -1}; int dy[4] {1, 0, -1, 0};可以极其方便地处理向上下左右四个方向的移动避免了写四个冗余的if语句。状态数组尺寸你代码中定义了int st[350][350]。这是一个非常稳妥的做法因为根据 LeetCode 200 题的数据范围网格大小通常不会超过300×300300 \times 300300×300350 的固定大小足以防止越界且省去了动态申请空间的开销。 C 代码实现classSolution{public:intm,n;// 定义方向数组分别代表上、右、下、左四个方向intdx[4]{0,1,0,-1};intdy[4]{1,0,-1,0};intnumIslands(vectorvectorchargrid){// 1. 初始化网格的行数和列数mgrid.size(),ngrid[0].size();// 2. 定义状态数组visited 数组350x350 足够容纳题目数据intst[350][350]{0};// 初始化为 0表示未访问intres0;// 记录岛屿数量// 3. 遍历整个二维网格for(inti0;im;i){for(intj0;jn;j){// 如果当前格子是陆地 1 且没有被访问过if(grid[i][j]1!st[i][j]){// 找到了一个新的岛屿起点岛屿数量 1res;// 发动 DFS将这座岛屿连通的所有陆地全部标记为已访问dfs(i,j,grid,st);}}}returnres;}// 辅助函数深度优先搜索用于“灌溉”标记整座岛屿voiddfs(intx,inty,vectorvectorchargrid,intst[350][350]){// 1. 将当前格子标记为已访问st[x][y]1;// 2. 尝试向四个方向蔓延for(inti0;i4;i){intxxxdx[i],yyydy[i];// 3. 边界检查和有效性检查// - xx, yy 必须在网格范围内// - 网格内容必须是陆地 1// - 该格子必须没有被访问过if(xx0xxmyy0yyngrid[xx][yy]1!st[xx][yy]){// 递归进行 DFSdfs(xx,yy,grid,st);}}}};