题目给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。思路这道题目求解的其实是连通图数量不同的岛屿属于不同的连通图 当遍历到其中一个岛屿时把这个岛屿给淹了全部变成0遇到水都跳过那么当遍历到另一个陆地时就是另一个岛屿执行同样的操作如此进行直到所有的陆地全部被淹。C#includeiostream#includevectorusingnamespacestd;classSolution{private:intm,n;public:voiddfs(vectorvectorchargrid,inti,intj){// 若越界或是水的情况if(i0||im||j0||jn||grid[i][j]0){return;}// 岛屿淹没为水grid[i][j]0;// 四个方向dfsdfs(grid,i1,j);dfs(grid,i-1,j);dfs(grid,i,j1);dfs(grid,i,j-1);}intnumIsLand(vectorvectorchargrid){if(m0)return0;// 网格大小为0intmgrid.size();intngrid[0].size();intcount0;for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){count;// 每发现一个岛屿。数量1dfs(grid,i,j);// dfs将岛屿淹没}}}returncount;}};python:方法一classSolution:defnumIslands(self,grid):mlen(grid)nlen(grid[0])res0defdfs(x,y):ifgrid[x][y]1:grid[x][y]0else:returnifx0:dfs(x-1,y)ifxm-1:dfs(x1,y)ify0:dfs(x,y-1)ifyn-1:dfs(x,y1)foriinrange(m):forjinrange(n):ifgrid[i][j]1:dfs(i,j)res1returnres方法二defnumIslands(grid):ifnotgrid:return0count0rows,colslen(grid),len(grid[0])defdfs(r,c):# 边界检查及是否为水的判断ifr0orc0orrrowsorccolsorgrid[r][c]0:return# 标记已访问原地修改为0以节省空间grid[r][c]0# 深度优先搜索四个方向dfs(r1,c)dfs(r-1,c)dfs(r,c1)dfs(r,c-1)foriinrange(rows):forjinrange(cols):# 找到陆地起点发起一次 DFS 连通分量遍历ifgrid[i][j]1:dfs(i,j)count1returncount