433. 岛屿的个数遍历加递归
433. 岛屿的个数遍历加递归
和蔼的zhxing
发布于 2018-09-04 11:33:05
发布于 2018-09-04 11:33:05
给一个01矩阵，求不同的岛屿的个数。 0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
样例 在矩阵：
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]中有 3 个岛.
遍历加递归
这个问题是图像处理中经常要用到的一个问题，即找连通域，用递归做起来其实还算比较简单，主要的思路就是：遍历到一个1时，把1周围的所有1都置零，这种置零是4邻域（题目中说只考虑上下左右相邻），而且应该是个递归的，也就是说一直置零到周围没有1为止，每进行一次这样的递归，就要进行一次计数，知道遍历完整个矩阵。其实实际图像处理中我们经常是要考虑八邻域的相邻。 需要注意的一个细节我注释了，递归终止条件应该是出界。
int numIslands(vector<vector<bool>> &grid) {
int m=grid.size();
if(m==0)
return 0;
int n=grid[0].size();
if(n==0)
return 0;
int res=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==true)
{
//cout<<i<<","<<j<<endl;
resetRound(grid,i,j);
res++;
}
}
}
return res;
// write your code here
}
void resetRound(vector<vector<bool>> &v,int i,int j)
{
int m=v.size();
int n=v[0].size();
if(i<0||i>=m||j<0||j>=n) //这里一定是要出边界而不能是在边界上
return ;
if(v[i][j]==true)
{
v[i][j]=false;
resetRound(v,i-1,j);
resetRound(v,i+1,j);
resetRound(v,i,j-1);
resetRound(v,i,j+1);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.01.31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读