leetcode-200-岛屿的个数（dfs找所有的连通分量）
leetcode-200-岛屿的个数（dfs找所有的连通分量）
chenjx85
发布于 2018-09-29 15:23:55
发布于 2018-09-29 15:23:55
题目描述：
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1示例 2:
输入:
11000
11000
00100
00011
输出: 3要完成的函数：
int numIslands(vector<vector<char>>& grid)
说明：
1、这道题给定一个二维的vector，char类型的数据，其中'1'表示陆地，'0'表示水域，要求返回陆地的个数。
2、这道题其实就是计算有多少个连通分量。那我们用dfs递归，一个连通分量完成一次dfs，我们在dfs过程中顺便给找到的位置标记一下，避免重复查找。
接着再在给定的二维vector中找到之前没有标记的并且为'1'的数据，继续下一次dfs递归……
接着再重复上述操作，找到所有的连通分量。
代码如下：（附详解）
void dfs(int i,int j,vector<vector<char>>& grid,vector<vector<bool>>& flag,int& hang,int& lie)
{
if(i>0&&grid[i-1][j]=='1'&&flag[i-1][j]==0)//上一行
{
flag[i-1][j]=1;
dfs(i-1,j,grid,flag,hang,lie);
}
if(i<hang-1&&grid[i+1][j]=='1'&&flag[i+1][j]==0)//下一行
{
flag[i+1][j]=1;
dfs(i+1,j,grid,flag,hang,lie);
}
if(j>0&&grid[i][j-1]=='1'&&flag[i][j-1]==0)//前一列
{
flag[i][j-1]=1;
dfs(i,j-1,grid,flag,hang,lie);
}
if(j<lie-1&&grid[i][j+1]=='1'&&flag[i][j+1]==0)//后一列
{
flag[i][j+1]=1;
dfs(i,j+1,grid,flag,hang,lie);
}
}
int numIslands(vector<vector<char>>& grid)
{
if(grid.empty())return 0;//边界条件，grid是空的
int hang=grid.size(),lie=grid[0].size(),count=0;
vector<vector<bool>>flag(hang,vector<bool>(lie,0));//初始化所有标记为0
for(int i=0;i<hang;i++)//循环查找陆地
{
for(int j=0;j<lie;j++)
{
if(flag[i][j]==0&&grid[i][j]=='1')//找到陆地，并且这块陆地没有被标记过
{
flag[i][j]=1;//进入递归之前先标记一下这块陆地
dfs(i,j,grid,flag,hang,lie);//进入递归
count++;//完成一次连通分量的递归，count++
}
}
}
return count;
}上述代码实测8ms，beats 98.85% of cpp submissions。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-09-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录