433. 岛屿的个数

作者: 和蔼的zhxing | 来源:发表于2018-01-31 15:27 被阅读11次

给一个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);
        }
    }

相关文章

  • 433. 岛屿的个数

    给一个01矩阵,求不同的岛屿的个数。0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左...

  • js刷林扣 lintcode(2017年7月~8月)

    433.岛屿的个数 (7.2) 给一个01矩阵,求不同的岛屿的个数。 0代表海,1代表岛,如果两个1相邻,那么这两...

  • 岛屿个数

    题目给定一个m行n列的二维地图,初始化每个单元都是水,操作addLand把单元格(row,col)变成陆地。岛屿定...

  • 岛屿的个数

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或...

  • 岛屿的个数

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或...

  • 岛屿的个数

    这题考察广度优先遍历和深度优先遍历,利用递归的方式做还算比较简单,但是输出的格式有待斟酌! 几个岛(滴滴) 题目:...

  • 岛屿的个数

    题目 思路:搜索到陆地(1)以后向前后以及下方遍历直至搜到海(0),将搜索到的陆地全部置为0并且将岛屿数量+1。

  • LeetCode:岛屿的个数

    岛屿的个数 题目叙述: 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围...

  • 11 - Medium - 岛屿的个数

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或...

  • 200. 岛屿的个数

    题目描述 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过...

网友评论

  • Zszen:感觉用opencv处理分分钟的事 哈哈, 算法看不懂
    和蔼的zhxing:@Zszen 这就相当于查找连通域的底层算法了,opencv直接查找肯定是最方便的

本文标题:433. 岛屿的个数

本文链接:https://www.haomeiwen.com/subject/nhxlzxtx.html