200. Number of Islands

Given a 2d grid map of'1's (land) and'0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

S1: Union Find

将二维矩阵转化为一维数组来表示union find的集合

class Solution {
public:
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    void initiate(int m, int n) {
        count = m * n;
        father = vector<int>(m * n, -1);
    }

    void connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
            count--;
        }
    }

    int find(int x) {
        if (father[x] == -1) {
            return x;
        }
        return father[x] = find(father[x]);
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if (m < 1) {
            return 0;
        }
        int n = grid[0].size();
        initiate(m, n);
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                            connect(x * n + y, i * n + j);
                        }
                    }
                } else {
                    count--;
                }
            }
        }
        return count;
    }

private:
    vector<int> father;
    int count;
};

S2: DFS O(m*n)

DFS查找所有1相邻’1‘节点，并置为0

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if (m < 1) {
            return 0;
        }
        int count = 0;
        int n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    count++;
                    dfsClean(grid, i, j);
                }
            }
        }
        return count;
    }

    void dfsClean(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() 
            || grid[i][j] == '0') {
                return;
        }
        grid[i][j] = '0';
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        for (int k = 0; k < 4; ++k) {
            int x = i + dx[k];
            int y = j + dy[k];
            dfsClean(grid, x, y);
        }
    }
};

305. Number of Islands II

A 2d grid map ofmrows andncolumns is initially filled with water. We may perform anaddLandoperation which turns the water at position (row, col) into a land. Given a list of positions to operate,count the number of islands after eachaddLandoperation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Givenm = 3, n = 3,positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d gridgridis filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array:[1, 1, 2, 3]

S: Union find

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> result;
        if (m < 1 || n < 1) {
            return result;
        }
        initiate(m ,n);
        vector<int> dx{0, 1, 0, -1};
        vector<int> dy{1, 0, -1, 0};
        vector<vector<bool>> island(m, vector<bool>(n, false));
        for (const auto& pos : positions) {
            int x = pos.first;
            int y = pos.second;
            island[x][y] = true;
            count++;
            for (int i = 0; i < 4; ++i) {
                int xi = x + dx[i];
                int yi = y + dy[i];
                if (xi >= 0 && xi < m && yi >= 0 && yi < n && island[xi][yi]) {
                    connect(x * n + y, xi * n + yi);
                }
            }
            result.push_back(count);
        }
        return result;
    }

    void initiate(int m, int n) {
        father = vector<int>(m * n, -1);
        count = 0;
    }

    int find(int a) {
        if (father[a] == -1) {
            return a;
        }
        return father[a] = find(father[a]);                                          
    }

    void connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father[root_a] = root_b;
            count--;
        }
    }

private:
    vector<int> father;
    int count;
};