[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;
    }
};