题目描述给你一个由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.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 ‘0’ 或 ‘1’解题思路总览方法核心思想时间复杂度空间复杂度备注DFS深度优先搜索从每个未访问的陆地开始遍历O(m*n)O(m*n)推荐解法BFS广度优先搜索用队列逐层扩展O(m*n)O(m*n)思路类似并查集将陆地进行合并O(m*n * alpha)O(m*n)较复杂迭代 DFS用栈模拟递归O(m*n)O(m*n)避免递归栈溢出一、核心解法DFS深度优先搜索核心思想遍历整个网格遇到未访问的陆地 ‘1’ 时就找到了一个新岛屿然后从这个位置出发深度优先搜索把所有相邻的陆地都标记为已访问。核心步骤 1. 遍历网格每个位置 2. 遇到未访问的 1岛屿数 1 3. 从该位置出发 DFS标记所有相连的 1 4. 继续遍历重复上述过程关键洞察为什么 DFS 能解决问题 因为岛屿的定义是相邻上下左右的陆地连成的区域。 当我们找到一个未访问的陆地 1 时 - 它是一个新岛屿的起点 - 通过 DFS 可以找到所有和它相连的陆地 - 这些陆地都属于同一个岛屿 遍历完成后所有陆地都被标记岛屿数量就是答案。图解grid [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ] 遍历过程 初始: visited 全部为 false ans 0 (i0, j0): grid[0][0]1, 未访问 ans 1 DFS(0,0): 标记 [0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2] visited: 第一行全标记第二行前两列标记第三行前两列标记 (i0, j1-3): 已被访问跳过 (i0, j4): 0跳过 (i1, j0-4): 已被访问跳过 (i2, j0-4): 已被访问跳过 (i3, j0-4): 全为 0跳过 输出: ans 1grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 遍历过程 初始: visited 全部为 false ans 0 (i0, j0): grid[0][0]1, 未访问 ans 1 DFS(0,0): 标记 [0,0],[0,1],[1,0],[1,1] visited: 左上角 2x2 区域 (i0, j2-4): 0 或已访问跳过 (i1, j2-4): 跳过 (i2, j0-1): 0跳过 (i2, j2): grid[2][2]1, 未访问 ans 2 DFS(2,2): 标记 [2,2] (i2, j3-4): 已访问或 0 (i3, j0-2): 0跳过 (i3, j3): grid[3][3]1, 未访问 ans 3 DFS(3,3): 标记 [3,3],[3,4] visited: 右下角 2x2 区域 输出: ans 3二、算法流程图输入: grid [ [1,1,1], [1,1,0], [0,0,1] ] 初始化: visited [[false,false,false], [false,false,false], [false,false,false]] ans 0 dir [[-1,0],[0,-1],[1,0],[0,1]] // 上左下右 遍历 (i0, j0): grid[0][0]1, visited[0][0]false ans 1 DFS(0,0): visited[0][0]true 尝试上: i-1, 越界 尝试左: j-1, 越界 尝试下: (1,0)1, 未访问 - DFS(1,0) visited[1][0]true 上下左右探索 - 递归到 (0,0), (2,0), (1,1) 尝试右: (0,1)1, 未访问 - DFS(0,1) visited[0][1]true 继续探索... 遍历完成: ans 2 (两个岛屿) 输出: 2三、完整代码实现classSolution{public:intnumIslands(vectorvectorchargrid){if(grid.empty())return0;intmgrid.size();intngrid[0].size();vectorvectorboolvisited(m,vectorbool(n,false));// 方向上、左、下、右intdir[4][2]{{-1,0},{0,-1},{1,0},{0,1}};functionvoid(int,int)dfs[](inti,intj){// 如果已经访问过直接返回if(visited[i][j])return;// 标记为已访问visited[i][j]true;// 尝试四个方向for(intk0;k4;k){intiiidir[k][0];intjjjdir[k][1];// 检查越界和是否为陆地if(ii0||iim||jj0||jjn)continue;if(grid[ii][jj]0)continue;// 递归搜索dfs(ii,jj);}};intans0;// 遍历整个网格for(inti0;im;i){for(intj0;jn;j){// 找到未访问的陆地就是新岛屿if(grid[i][j]1!visited[i][j]){ans;dfs(i,j);}}}returnans;}};四、逐行解析if(grid.empty())return0;处理空网格的特殊情况intmgrid.size();intngrid[0].size();vectorvectorboolvisited(m,vectorbool(n,false));m, n网格的行数和列数visited记录每个位置是否被访问过intdir[4][2]{{-1,0},{0,-1},{1,0},{0,1}};四个方向的偏移量上、左、下、右functionvoid(int,int)dfs[](inti,intj){定义 DFS 函数用 lambda 方便递归调用if(visited[i][j])return;visited[i][j]true;如果已经访问过直接返回避免重复访问否则标记为已访问for(intk0;k4;k){intiiidir[k][0];intjjjdir[k][1];if(ii0||iim||jj0||jjn)continue;if(grid[ii][jj]0)continue;dfs(ii,jj);}遍历四个方向越界检查和是否为陆地的检查递归搜索相邻的陆地if(grid[i][j]1!visited[i][j]){ans;dfs(i,j);}如果遇到未访问的陆地说明发现了新岛屿ans然后从该位置开始 DFS 标记整个岛屿五、DFS 的原理DFS 的核心思想沿着一条路走到底然后回溯。 对于岛屿问题 1. 从起点出发把起点标记为已访问 2. 依次尝试四个方向 3. 如果相邻位置是未访问的陆地递归进入 4. 每个位置只会被访问一次 类似染色的过程 - 找到一个未染色陆地染成新颜色 - 递归把所有相邻的陆地染成同样的颜色 - 继续找下一个未染色陆地六、与并查集对比维度DFS并查集代码复杂度简单较复杂时间复杂度O(m*n)O(m*n * alpha)空间复杂度O(m*n)O(m*n)实现方式递归或栈数组 路径压缩适用场景岛屿、连通区域需要动态合并的场景七、复杂度分析方法时间复杂度空间复杂度备注DFSO(m*n)O(m*n)推荐递归深度最多 m*nBFSO(m*n)O(m*n)用队列存储并查集O(m*n)O(m*n)较复杂迭代 DFSO(m*n)O(m*n)避免递归栈溢出详细分析时间复杂度 每个格子最多被访问一次 每次访问时进行常数次操作 总计O(m*n) 空间复杂度 visited 数组O(m*n) 递归栈深度最坏 O(m*n)当整个网格都是陆地时 总计O(m*n)八、边界情况分析情况处理方式空网格return 0全是水 (‘0’)return 0全是陆地 (‘1’)return 1单个陆地return 1网格只有一行正常处理网格只有一列正常处理示例全是水grid [ [0,0,0], [0,0,0] ] 遍历 所有位置都是 0不满足 grid[i][j] 1 ans 0 输出: 0示例全是陆地grid [ [1,1,1], [1,1,1] ] 遍历 (0,0): 发现新岛屿ans1DFS 标记整个网格 剩余位置都已访问 输出: 1九、面试追问 FAQ问题回答要点Q: 为什么需要 visited 数组防止重复访问同一个位置导致无限递归或重复计数Q: 能否不用 visited可以原地修改 grid但会破坏输入数据Q: 递归深度太大怎么办用栈模拟递归或者 BFSQ: 时间复杂度为什么是 O(m*n)每个格子最多被访问一次Q: 能否用 BFS 代替 DFS可以BFS 用队列DFS 用栈或递归Q: 四个方向的顺序重要吗不重要只要遍历完四个方向即可十、相关题目题目编号题目名称难度核心差异200岛屿数量中等基础题统计岛屿个数695岛屿的最大面积中等求最大岛屿面积463岛屿的周长简单求岛屿周长694不同岛屿的数量困难求不同形状岛屿数量剑指 Offer 13机器人的运动范围中等BFS/DFS 条件限制79单词搜索中等DFS 回溯十一、总结要点内容核心思想遍历网格遇到未访问的陆地就计数并 DFS 标记关键数据结构visited 数组防止重复访问方向数组dir[4][2] {{-1,0},{0,-1},{1,0},{0,1}}时间复杂度O(m*n)每个格子最多访问一次空间复杂度O(m*n)visited 递归栈变形求岛屿面积统计岛屿内格子数、求岛屿周长易错点越界检查、visited 判断岛屿数量是经典的连通区域问题通过 DFS/BFS 遍历网格标记已访问的陆地统计连通区域的数量。