给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

Solution

回溯算法入门级详解

参考 @liuyubobobo 、@liweiwei1419 、@jyd

• floodfill

Flood fill 算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典 算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在 GNU Go 和 扫雷 中，Flood Fill算法被用来计算需要被清除的区域。

• 深度优先搜索，回溯法

// @lc code=start
class Solution {
private:
    int d[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    int m, n;
    vector<vector<bool>> visited;

    bool inArea(int x, int y){
        return x>=0 && x<m && y>=0 && y<n;
    }

    // 从grid[x][y]的位置开始,进行floodfill
    // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
    void dfs(vector<vector<char>>& grid, int x, int y){
        visited[x][y] = true;
        for(int i=0; i<4; ++i){
            int newx = x+d[i][0];
            int newy = y+d[i][1];
            if(inArea(newx,newy) && !visited[newx][newy] && grid[newx][newy]=='1')
                dfs(grid, newx, newy);
        }
        return;
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        if(m==0) return 0;
        n = grid[0].size();
        if(n==0) return 0;

        for(int i=0; i<m; ++i)
            visited.push_back(vector<bool>(n, false));
        
        int res=0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                // 保证(x,y)合法,且grid[x][y]是没有被访问过的陆地
                if(grid[i][j]=='1' && !visited[i][j]){
                    dfs(grid, i, j);
                    res += 1;
                }
            }
        }
        return res;
    }
};
// @lc code=end

• 广度优先搜索
• 借用一个队列 queue，判断队列首部节点 (i, j) 是否未越界且为 1：
  • 若是则置零（删除岛屿节点），并将此节点上下左右节点加入队列；
  • 若不是则跳过此节点；
• 循环 pop 队列首节点，直到整个队列为空，此时已经遍历完此岛屿。

class Solution {
private:
    int d[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    int m, n;
    vector<vector<bool>> visited;

    bool inArea(int x, int y){
        return x>=0 && x<m && y>=0 && y<n;
    }

    void bfs(vector<vector<char>>& grid, int x, int y){
        queue<pair<int,int>> q;
        q.push({x,y});
        while(!q.empty()){
            auto pos = q.front();
            q.pop();
            int x = pos.first, y = pos.second;
            if(inArea(x,y) && !visited[x][y] && grid[x][y]=='1'){
                visited[x][y] = true;
                for(int i=0; i<4; ++i){
                    int newx = x+d[i][0];
                    int newy = y+d[i][1];
                    q.push({newx, newy});
                }
            }
        }
        return;
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        if(m==0) return 0;
        n = grid[0].size();
        if(n==0) return 0;

        for(int i=0; i<m; ++i)
            visited.push_back(vector<bool>(n, false));
        
        int res=0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1' && !visited[i][j]){
                    bfs(grid, i, j);
                    res += 1;
                }
            }
        }
        return res;
    }
};

• 并查集
• 扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。

class UnionFind{
public:
    UnionFind(vector<vector<char>>& grid){
        size = 0;
        int m = grid.size();
        int n = grid[0].size();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1'){
                    parent.push_back(i*n + j);
                    ++size;
                }
                else 
                    parent.push_back(-1);
                rank.push_back(0);
            }
        }
    }

    int getSize() const {
        return size;
    }

    int find(int i){
        if(i != parent[i])
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void unite(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot != qRoot){
            // 基于 rank 优化
            if(rank[pRoot] < rank[qRoot]){
                parent[pRoot] = qRoot;
            } else if(rank[pRoot] > rank[qRoot]){
                parent[qRoot] = pRoot;
            } else {
                parent[qRoot] = pRoot;
                rank[pRoot] += 1;
            }
            --size;
        }
    }

private:
    vector<int> parent;
    vector<int> rank;
    int size;  // 表示连通分量的数目
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        UnionFind uf(grid);
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
                    if (r + 1 < nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
                    if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
                    if (c + 1 < nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
                }
            }
        }

        return uf.getSize();
    }
};