一道题目引发的扩展……

岛屿的数量

题目

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

示例

1

输入:
11110
11010
11000
00000

输出: 1

2

输入:
11000
11000
00100
00011

输出: 3

思路与实现过程

这道题隶属于Leetcode上的并查集分类，于是便有了写成二维并查集的思路
与以前father[x]和x的一一对应关系不同，现在需要对应的是点坐标(x,y)
在实现过程中可以使用pair<int,int> 定义于Utility
也可以定义结构体struct point{int x,y;};
然后开一个二维数组使用2个坐标参数去访问
这样下来二维并查集的问题便迎刃而解了
那么怎么计算岛屿个数呢?
其实也很简单，只需要判断当一个方块是陆地('1')时,它父节点是本身的有多少点
还有一个问题讲述的是岛屿面积
在每次合并时候为对应的area数组对应位置分别加一就好

代码

class Solution
{
  public:
    vector<vector<pair<int, int>>> father;
    int size_x;
    int size_y;

    pair<int, int> find(pair<int, int> p)
    {
        return father[p.first][p.second] == p
                   ? p
                   : father[p.first][p.second] = find(father[p.first][p.second]);
    }

    void merge(int ax, int ay, int bx, int by)
    {
        pair<int, int> a(ax, ay);
        pair<int, int> b(bx, by);
        a = find(a);
        b = find(b);
        if(a == b) return;
        father[a.first][a.second] = b;
        return;
    }

    int num_of_set(vector<vector<char>> &grid)
    {
        int ans = 0;
        for (int i = 0; i < size_x; i++)
            for (int j = 0; j < size_y; j++)
                if (father[i][j].first == i && father[i][j].second == j && grid[i][j] == '1')
                    ans++;
        return ans;
    }

    void init(vector<vector<char>> &grid)
    {
        if (grid.empty() && grid[0].empty())
            return;
        size_x = grid.size();
        size_y = grid[0].size();

        for (int i = 0; i < size_x; i++)
        {
            vector<pair<int, int>> p;
            vector<int> a;
            for (int j = 0; j < size_y; j++)
            {
                a.push_back(1);
                pair<int, int> q(i, j);
                p.push_back(q);
            }
            area.push_back(a);
            father.push_back(p);
        }
    }

    int numIslands(vector<vector<char>> &grid)
    {
        if(grid.empty()) return 0;
        init(grid);
        for (int i = 0; i < size_x; i++)
        {
            for (int j = 0; j < size_y; j++)
            {
                if (grid[i][j] == '1')
                {
                    if (i > 0 && grid[i - 1][j] == '1')
                        merge(i, j, i - 1, j);
                    if (i < size_x - 1 && grid[i + 1][j] == '1')
                        merge(i, j, i + 1, j);
                    if (j > 0 && grid[i][j - 1] == '1')
                        merge(i, j, i, j - 1);
                    if (j < size_y - 1 && grid[i][j + 1] == '1')
                        merge(i, j, i, j + 1);
                }
            }
        }
        return num_of_set(grid);
    }
};