【LeetCode200】岛屿数量（求连通分量个数）

【LeetCode200】岛屿数量（求连通分量个数）

1.题目

2.思路

（1）本质就是用dfs遍历求图的连通分量个数（之前做过类似的——​​【LeetCode79】单词搜索​​​）dfs注意base case和递归体。 base case是非1字符和非网格外位置，如果“判断是否网格内”写在base case时后面的递归前就不用判断是否在网格内了；如果没写在base case，后面递归前就判断。

（2）如果不用这个directions的vector方向数组，就写4个dfs。

（3）为了防止重复遍历连通分量，需要将遍历过1的位置做标记——可以另外开个二维数组了，直接在grid二维数组上将元素1改为2或其他非1的数字都可。

（4）为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」（这个步骤就是​​grid[x][y]='2'​​，其实改成0也是可以的）呢？主要是为了省事，避免维护visited数组。因为dfs函数遍历到值为0的位置会直接返回，所以只要把经过的位置都设置为0，就可以起到不走回头路的作用。

PS：这类 DFS 算法还有个别名叫做 FloodFill 算法。

（5）岛屿题目是个系列，另外的几个题刷到再​​一起总结，看这篇题解​​​。 200. 岛屿数量 （Easy） 463. 岛屿的周长 （Easy） 695. 岛屿的最大面积 （Medium） 827. 最大人工岛 （Hard）

3.代码

class Solution {private: vector>directions{{0,1},{0,-1},{1,0},{-1,0}}; int num;//岛屿个数public: int numIslands(vector>& grid) { int row=grid.size();//row行数 int col=grid[0].size();//column列数 for(int i=0;i>&grid,int x,int y){ if(!isarea(grid,x,y)){ return;//如果坐标(x,y)超过网格范围，则直接返回 } if(grid[x][y]!='1'){ return;//如果不是岛屿(1)则直接返回 } grid[x][y]='2';//将格子标记为已遍历过 for(auto dir:directions){ int newx=x+dir.first,newy=y+dir.second; if(isarea(grid,newx,newy)){//在网格范围内(正常) dfs(grid,newx,newy); } } } bool isarea(vector>&grid,int x,int y){//判断点是否在网格内 if(x>=0 && x

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。