思路1：BFS

• 逐个扫描矩阵，如果发现有1，那么计数器cnt就 +1
• 然后将这个发现的1的所有相邻的1全部变成0
• 逐个重复这个操作
• 需要注意的是，BFS在将新节点插入的时候就要改变数值，否则会有重复扫描的问题。

代码1：

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    void bfs(vector<vector<char>>& grid, int x, int y, int row, int col) {
        queue<pair<int, int>> queue_pos;
        queue_pos.push({x, y});
        while (!queue_pos.empty()) {
            int cur_level_size = queue_pos.size();
            for (int i = 0; i < cur_level_size; ++i) {
                pair<int, int> cur_pos = queue_pos.front();
                queue_pos.pop();
                int cur_x = cur_pos.first;
                int cur_y = cur_pos.second;
                //grid[cur_x][cur_y] = '0';
                // 考虑将新节点放到树上
                for (int i = 0; i < 4; i++) {
                    int next_x = cur_x + dx[i];
                    int next_y = cur_y + dy[i];
                    if (next_x < 0 || next_x >= row || next_y < 0 || next_y >= col || grid[next_x][next_y] == '0') {
                        continue;
                    } else {
                        // 此处的0起到标记的作用，防止重复访问
                        grid[next_x][next_y] = '0';
                        queue_pos.push({next_x, next_y});
                    }
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        if (!grid.size()) {
            return 0;
        }
        int cnt = 0;
        int row = grid.size();
        int col = grid[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    cnt++;
                    bfs(grid, i, j, row, col);
                }
                // cout << grid[i][j] << " ";
            }
            // cout << endl;
        }
        return cnt;
    }
};

思路2：栈式DFS

• 在弹栈的时候加入序列（也就是变成0）
• 和先序遍历二叉树的思路一样
• 根节点先入栈，然后弹栈，最后将可能的节点都加入栈中

• 脑子里面要有图，不然记不住。

  代码2：

  class Solution {
  public:
    void stackDfs(vector<vector<char>>&grid, int x, int y, int row, int col) {
        int dx[4] = {1, 0, -1, 0};
        int dy[4] = {0, -1, 0, 1};
        stack<pair<int, int>> stack_islands;
        stack_islands.push({x, y});
        while (!stack_islands.empty()) {
            // 出栈时加入遍历序列（这里就是变成0了）
            pair<int, int> cur_pos = stack_islands.top();
            int cur_x = cur_pos.first, cur_y = cur_pos.second;
            stack_islands.pop();
            grid[cur_x][cur_y] = '0';
            // 入栈
            for (int i = 0; i < 4; ++i) {
                int next_x = cur_x + dx[i], next_y = cur_y + dy[i];
                if (next_x >= 0 && next_x < row && next_y >= 0 && next_y < col && grid[next_x][next_y] == '1') {
                    stack_islands.push({next_x, next_y});
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        int count_islands = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == '1') {
                    count_islands++;
                    stackDfs(grid, i, j, row, col);
                }
            }
        }
        return count_islands;
    }
  };

  思路3：并查集

• 利用node(i, j) = i * col + j将二维的点变成一维的数字

• 遍历grid当中每一个元素，如果是'1'，那么就和它上下左右所有的‘1’放到一个集合当中。
• 遍历grid当中每一个元素，如果find(node(i,j)) == node(i, j) && grid[i][j] == 1，说明一定是一个新的集合。统计个数即可。

• 并查集操作可以按秩进行优化。

  代码3：

  class Solution {
  private:
    int row, col;
    unordered_map<int, int> fa, r;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
  public:
    bool check_boundary(int x, int y) {
        if (0 <= x && x <= row - 1 && 0 <= y && y <= col - 1) {
            return true;
        } else {
            return false;
        }
    }
    void init(int n) {
        for (int i = 0; i <= n; i++) {
            fa[i] = i;
            r[i] = 1;
        }
    }
    int find(int x) {
        if (x == fa[x]) {
            return x;
        } else {
            fa[x] = find(fa[x]);
            return fa[x];
        }
    }
    void merge(int i, int j) {
        int x = find(i);
        int y = find(j);
        if (x != y) {
            if (r[x] <= r[y]) {
                fa[x] = y;
            } else {
                fa[y] = x;
            }
            if (r[x] == r[y]) {
                r[y] += 1;
            }
        }
    }
    int node(int i, int j) {
        return i * col + j;
    }
    int numIslands(vector<vector<char>>& grid) {
        row = grid.size(), col = grid[0].size();
        init(row * col + 5);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    for (int k = 0; k < 4; k++) {
                        int ni = i + dx[k], nj = j + dy[k];
                        if (check_boundary(ni, nj) && grid[ni][nj] == '1') {
                            merge(node(i, j), node(ni, nj));
                        }
                    }
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (find(node(i, j)) == node(i, j) && grid[i][j] == '1') {
                    cnt += 1;
                }
            }
        }
        return cnt;
    }
  };