[C++] LeetCode 200. 岛屿的个数

题目

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:

11110

11010

11000

00000

输出: 1

示例 2:

输入:

11000

11000

00100

00011

输出: 3

题解

这道题考察岛屿的个数，可以基于深度优先搜索或者广度优先搜索，或者并查集来做，这里提供两种解法。

方法一

采用DFS，对二维数组进行比遍历，遇到

1

则找到一个岛屿，然后把与之关联的位置全部置为

2

，那么对二维数组完成一次遍历，即可得出结果。代码如下：

class Solution {
public:
    void setOne(vector<vector<char>> &grid,int row,int col){
        int m=grid.size();
        int n=grid[].size();
        if((row<)||(row>=m)||(col<)||(col>=n)||(grid[row][col]!='1')){
            return;
        }
        grid[row][col]=;
        setOne(grid,row+,col);
        setOne(grid,row-,col);
        setOne(grid,row,col+);
        setOne(grid,row,col-);
    }
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size();
        if(m==) return ;
        int n=grid[].size();
        if(n==) return ;
        int sum=;
        for(int i=;i<m;i++){
            for(int j=;j<n;j++){
                if(grid[i][j]=='1'){
                    sum++;
                    setOne(grid,i,j);
                }
            }
        }
        return sum;
    }
};
           

方法二 并查集

也可以考虑用并查集来做这题，将二维数组重新编号，从

开始，从左到右，从上到下，直到

n*m-1

（其中

n

为行数，

m

为列数），对于位置

(i,j)

则编号为

i*m+j

，那么相邻（左右，上下）的为同一个值，则认为他们相通。那么最终只要统计一下

father[i]==i

且对应值为

1

的个数即可。代码如下：

class Solution {
public:
    int findFather(vector<int> &father,int a){
        int f=a;
        while(father[f]!=f){
            f=father[f];
        }
        while(father[a]!=a){
            int z=a;
            a=father[z];
            father[a]=f;

        }
        return f;
    }
    void unionFather(vector<int> &father, int a,int b){
        int fa=findFather(father,a);
        int fb=findFather(father,b);
        if(fa!=fb){
            father[fa]=fb;
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==||grid[].size()==) return ;
        int n=grid.size(),m=grid[].size(),k=n*m;
        vector<int> father(k,-);
        for(int i=;i<k;i++){
            father[i]=i;
        }
        for(int i=;i<n;i++){
            for(int j=;j<m;j++){
                int t1=i*m+j;
                int t2=t1+,t3=t1+m;
                if(j+<m&&grid[i][j]==grid[i][j+]) unionFather(father,t1,t2);
                if(i+<n&&grid[i][j]==grid[i+][j]) unionFather(father,t1,t3);
            }
        }
        int res=;
        for(int i=;i<k;i++){
            if(father[i]==i&&grid[i/m][i%m]=='1'){
                res+=;
            }
        }
        return res;
    }
};