lintcode程序员

433. 岛屿的个数

2018-01-31  本文已影响11人  和蔼的zhxing

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

猜你喜欢

热点阅读