题解 | #岛屿数量#

#include <cstring>
#include <type_traits>

class UnionFind{
private:
    // int *nums;
public:
    int *nums;
    UnionFind(int n){
        nums=new int[n];
        for(int i=0;i<n;i++)nums[i]=i;
    }
    ~UnionFind(){
        delete []  nums;
    }
    int find(int x){
        int k=x;
        while(nums[k]!=k){
            k=nums[k];
        }
        while(x!=k){
            int t=nums[x];
            nums[x]=k;
            x=t;
        }
        return x;
    }

    bool isHB(int x,int y){
        int a=find(x);
        int b=find(y);
        if(a!=b){
            nums[a]=b;
            return true;
        }

        return false;
    }
};

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */

    // int 
    int solve(vector<vector<char> >& grid) {
        // write code here
        int row=grid.size();
        if(row==0) return 0;
        int col=grid[0].size();
        if(col==0) return 0;

        int count=0;
        UnionFind U(row*col+1);
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]=='1'){
                    count++;
                    if(i+1<row && grid[i+1][j]=='1' && U.isHB(i*col+j, (i+1)*col+j)){
                        count--;
                    }
                    if(j+1<col && grid[i][j+1]=='1' && U.isHB(i*col+j, i*col+j+1)){
                        count--;
                    }
                }
                
            }
        }
        return count;
    }
};