LeetCode 200: 岛屿数量

[guodongxiaren]

https://leetcode-cn.com/problems/number-of-islands/

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

示例 1:

输入: 11110 11010 11000 00000

输出: 1

示例 2:

输入: 11000 11000 00100 00011

输出: 3

[guodongxiaren]

这道题和其他并查集问题不同的地方在于。虽然输入数据还是矩阵。 但是M[i][j]表示的已经不是i和j存在关系了。而是说这是这个点（岛屿）。 是否归并到集合，也不是看M[i][j]是否为1，还要看他周边的岛屿是否为1。 因为我们是从左到右，从上到下的移动下标。所以只需要看当前的岛屿的左侧和上方是否为1（岛）。 主要parent数组初始化的时候不能盲目parent[i] = i了！ 原先能这样做，是因为i肯定表示一个存在的元素。但是本题不是。

[guodongxiaren]

class Solution {
public:
    int *parent; // 岛屿个数差异比较大，最大个数 > 200000。所以用指针，不用固定大小的数组
    int find(int a) {
        if (parent[a] != a) {
            parent[a] = find(parent[a]);
        }
        return parent[a];
    }
    bool merge(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) {
            return false;
        }
        parent[pa] = pb;
        return true;
    }
    void init(int n) {
        parent = new int[n];
        memset(parent, -1, sizeof(int)*n);
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0 ) return  0;
        int R = grid.size();
        int C = grid[0].size();
        int ans = 0;
       init(R*C);
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                if (grid[i][j] == '1') {
                    parent[i*C+j] = i*C+j;
                    ans++;
                } else {
                    parent[i*C+j] = -1;
                }
            }
        }
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                if (grid[i][j] == '0') {
                    continue;
                }
                if (j > 0 && grid[i][j-1] == '1') {
                    ans -= merge(i*C+j-1, i*C+j);
                }
                if (i > 0 && grid[i-1][j] == '1') {
                    ans -= merge((i-1)*C+j, i*C+j);
                }
            }
        }
        return ans;
    }
};

[guodongxiaren]

其实也可以不用ans

class Solution {
public:
    int *parent; // 岛屿个数差异比较大，最大个数 > 200000
    int find(int a) {
        if (parent[a] != a) {
            parent[a] = find(parent[a]);
        }
        return parent[a];
    }
    bool merge(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) {
            return false;
        }
        parent[pa] = pb;
        return true;
    }
    void init(int n) {
        parent = new int[n];
        memset(parent, -1, sizeof(int)*n);
    }
    int root_num(int n) {
        int r = 0;
        for (int i = 0; i < n; ++i) {
            if (parent[i] == i) {
                r++;
            }
        }
        return r;
    }
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0 ) return  0;
        int R = grid.size();
        int C = grid[0].size();
        init(R*C);
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                if (grid[i][j] == '1') {
                    parent[i*C+j] = i*C+j;
                } else {
                    parent[i*C+j] = -1;
                }
            }
        }
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                if (grid[i][j] == '0') {
                    continue;
                }
                if (j > 0 && grid[i][j-1] == '1') {
                    merge(i*C+j-1, i*C+j);
                }
                if (i > 0 && grid[i-1][j] == '1') {
                    merge((i-1)*C+j, i*C+j);
                }
            }
        }
        return root_num(R*C);
    }
};