岛屿数量(递归or并查集)

题目描述：

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

way：用递归的方式去感染，每个位置最多被它上下左右的点遍历到，然后main遍历一遍所有的点，每个位置最多被遍历5遍，点的个数是m*n，所以时间复杂度是O(m * n)。

class Solution {
public:

    // 从(i,j)这个位置出发，把所有连成一片的'1'字符，变成'2'
    void infect(vector<vector<char>>& grid, int i, int j)
    {
        if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j] != '1') return;
        grid[i][j]='2';
        infect(grid, i+1, j);
        infect(grid, i-1, j);
        infect(grid, i, j+1);
        infect(grid, i, j-1);
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int result=0;
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[i].size(); j++)
            {
                if(grid[i][j] =='1')
                {
                    result++;
                    infect(grid, i, j);
                }
            }
        }
        return result;  
    }
};

way：将每个为'1'的点封成一个对象，然后每个对象的地址都不同，就是一个个不同的点，这个对象的地址就是每个点的值，然后利用并查集的值->node, node去做sizeMap或者parent之间的映射，DotList中包含了所有点对象的地址值用于初始化，然后board二维表中也让i,j位置能找到某个点对象的值，（有了值就能找到node, 就能去做并查集相关。）如果一个点对象的左边或者上边有'1'且自己是'1'，那么就能把这个点对象和左边的或上边的点合并到一个集合中，最后返回集合的个数是岛屿的个数。（这里点对象就是为一的不同的值，此时grid上的'1'和'0'只让我们用做逻辑使用，和编号值无关了属于是）。

#include<iostream>
#include<map>
#include<stack>
#include<vector>
using namespace std;

struct Dot
{

};


typedef Dot*  T;

struct Node
{
    T val;
    Node(T val)
    {
        this->val = val;
    }
};


class UnionFind
{
private:
    map<T, Node*> nodes;
    map<Node*, Node*>parents;
    map<Node*, int> sizeMap;

public:
    UnionFind(vector<T> vec)
    {
        for(auto dot : vec)
        {
            Node *node = new Node(dot);
			nodes[dot] = node;
            parents[node] = node;
            sizeMap[node] = 1;
        }
    }

    Node *findFather(Node * cur)
    {
        stack<Node*> path;
        while(cur != parents[cur])
        {
            path.push(cur);
            cur = parents[cur];
        }
        while(!path.empty())
        {
            parents[path.top()] = cur;
            path.pop();
        }
        return cur;
    }

    bool isSameSet(T a, T b)
    {
        Node *aNode = nodes[a];
        Node *bNode = nodes[b];
        return findFather(aNode) == findFather(bNode);
    }

    void Union(T a, T b)
    {
        Node *aFather = findFather(nodes[a]);
        Node *bFather = findFather(nodes[b]);
        if(aFather != bFather)
        {
            int aSize = sizeMap[aFather];
            int bSize = sizeMap[bFather];
            Node *big = aSize>=bSize?aFather:bFather;
            Node *small = big==aFather?bFather:aFather;
            parents[small] = big;
            sizeMap[big] = aSize+bSize;
            sizeMap.erase(small);
        }
    }

    int getNums()
    {
        return sizeMap.size();
    }
};


class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int r=grid.size(), c=grid[0].size();
        vector<vector<Dot*>>board = vector<vector<Dot*>>(r, vector<Dot*>(c,nullptr));
        vector<Dot*> dotList;
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                //这里的判断很关键
                if(grid[i][j]=='1')
                {
                    board[i][j] = new Dot();
                    dotList.push_back(board[i][j]);
                } 
            }
        }
        UnionFind uf(dotList);

//第一行 只有左边
        for(int j=1; j<c; j++)
        {
            if(grid[0][j-1]=='1' && grid[0][j] =='1')
            {
                uf.Union(board[0][j-1], board[0][j]);
            }
        }  

//第一列  只有上边
        for(int i=1; i<r; i++)
        {
            if(grid[i-1][0] =='1' && grid[i][0] == '1')
            {
                uf.Union(board[i-1][0], board[i][0]);
            }
        }

//其他行和列
        for(int i=1; i<r; i++)
        {
            for(int j=1; j<c; j++)
            {
                if(grid[i-1][j] =='1' && grid[i][j] == '1')
                {
                    uf.Union(board[i-1][j], board[i][j]);
                }

                if(grid[i][j-1] =='1' && grid[i][j] =='1')
                {
                    uf.Union(board[i][j-1], board[i][j]);
                }
            }
        }
        return uf.getNums();
    }
};

way：完全根据grid中点的位置i,j来得到 index = r*col +c index就作为了每个'1'点的编号值，然后也是如果某个点的上边和下边的点有'1'且自己是'1'就合并这些点到一个集合中，此时点因为编号不同都是不同的，所以parents和sizeMap用的都是<int,int>这样的映射（因为编号值此时确定了是个整型）, nodes不用映射就可以是自己本身的值。（此时grid上的'1'和'0'只让我们用做逻辑使用，和编号值无关了属于是）。

class UnionFind{
private:
    map<int,int>parents;
    map<int,int>sizeMap;
    vector<vector<char>> grid;
public:

    int getIndex(int r, int c)
    {
        int col= grid[0].size();
        return r*col+c;
    }

    UnionFind(vector<vector<char>>& grid)
    {
        int r=grid.size(),c=grid[0].size();
        this->grid = grid;
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                if(grid[i][j]=='1')
                {
                    int index = getIndex(i, j);
                    parents[index]=index;
                    sizeMap[index]=1;
                }    
            }
        }
    }

    int findFather(int index)
    {
        stack<int>path;
        while(index != parents[index])
        {
            path.push(index);
            index = parents[index];
        }
        while(!path.empty())
        {
            parents[path.top()]=index;
            path.pop();
        }
        return index;
    }

    void Union(int r1, int c1, int r2, int c2)
    {
        int index1= getIndex(r1, c1);
        int index2= getIndex(r2, c2);
        int aFather = findFather(index1);
        int bFather = findFather(index2);
        if(aFather != bFather)
        {
            int aSize = sizeMap[aFather];
            int bSize = sizeMap[bFather];
            int big = aSize>=bSize?aFather:bFather;
            int small= big==aFather?bFather:aFather;
            parents[small]=big;
            sizeMap[big]= aSize +bSize;
            sizeMap.erase(small);
        }
    }
    
    int getNums()
    {
        return sizeMap.size();
    }
};


class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        UnionFind uf(grid);
        int r=grid.size();
        int c=grid[0].size();
//第一行，只有左边
        for(int j=1; j<c; j++)
        {
            if(grid[0][j]=='1' && grid[0][j-1]=='1')
            {
                uf.Union(0,j,0,j-1);
            }
        }

//第一列，只有上边
        for(int i=1; i<r; i++)
        {
            if(grid[i][0]=='1' && grid[i-1][0]=='1')
            {
                uf.Union(i,0,i-1,0);
            } 
        }

//其他行和列
        for(int i=1; i<r; i++)
        {
            for(int j=1; j<c; j++)
            {
                if(grid[i][j]=='1')
                {
                    if(grid[i-1][j]=='1')
                    {
                        uf.Union(i,j,i-1,j);
                    }
                    if(grid[i][j-1]=='1')
                    {
                        uf.Union(i,j,i,j-1);
                    }
                }
            }
        }
        return uf.getNums();  
    }
};

so，关键的是，搞清楚并查集是以什么值为节点的标识的。虽然递归的方式是最简单的，但并查集也是可做的。至于为什么只用把一个'1'点的左边和上边的'1'合并到一个集合中，是因为每个点都是这么来的，所以每个点只用管自己的左边和上边是否能合并到一个集合里，合并完的集合数量就是岛的数量。