连通块（并查集和DFS做法）

解题思路一：DFS（深度优先搜索）

首先遍历整个方格图，当遇到一个黑色格子时，从该格子开始进行深度优先搜索，并将所有被搜索到的黑色格子涂成白色，表示已经被搜索过了。
在深度优先搜索的过程中，每次遇到一个黑色格子就将其上下左右的黑色格子加入搜索队列。
统计搜索的次数即可得到答案。

参考代码：时间复杂度:O(m*n)

#include<bits/stdc++.h>
using namespace std;
// 定义常量N，表示方格图的最大边长
const int N = 1010;
int n, m;   // 定义方格图的尺寸n和m
int g[N][N];   // 定义存储方格图的二维数组g
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 定义二维数组d，表示当前方向向上、下、左、右移动的偏移量
// 定义函数dfs，这个函数的功能是从当前位置(x, y)开始进行深度优先搜索，将所有被搜索到的黑色格子涂成白色
void dfs(int x, int y) {
    g[x][y] = 0;   // 将当前位置涂成白色
    // 遍历当前位置的四周
    for (int i = 0; i < 4; i ++ ) {
        int a = x + d[i][0], b = y + d[i][1];   // 计算当前方向的位置(a, b)
        // 判断(a, b)是否越界，并且(a, b)是否为黑色格子
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b]) {
            dfs(a, b);   // 从(a, b)开始进行深度优先搜索
        }
    }
}
int main() {
    cin >> n >> m;  // 输入方格图的尺寸
    // 输入方格图的具体内容
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            cin >> g[i][j];
        }
    }
    int ans = 0;   // 定义变量ans，表示连通块的数量
    // 遍历整个方格图
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            if (g[i][j]) { // 当前位置是黑色格子
                ans ++ ; // 连通块数量+1
                dfs(i, j); // 从(i, j)开始进行深度优先搜索，将所有被搜索到的黑色格子涂成白色
            }
        }
    }
    cout << ans << endl;  // 输出连通块的数量
    return 0;
}

解题思路二：并查集

我们可以将每个黑色格子看作一个节点，然后使用并查集来维护节点之间的关系。
首先，我们输入方格图的尺寸和具体内容，然后将每个节点的父节点初始化为其本身。
接下来，我们遍历整个方格图，对于每个黑色格子，我们检查其上、下、左、右四个位置是否也是黑色格子，如果是，则将这两个节点合并到同一个集合中。
最后，我们统计连通块的数量即可得到答案。
注意：在解决这道题时，我们需要注意的一个点是，当前的连通块可能不止包含一个黑色格子，因此我们在遍历方格图时，需要维护每个连通块的边界。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int g[N][N]; // 存储方格图
int f[N * N]; // 并查集数组
// 并查集的查找函数
int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}
// 并查集的合并函数
void merge(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    f[ra] = rb;
}
int main() {
    cin >> n >> m;
// 输入方格图
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            cin >> g[i][j];
        }
    }
// 初始化每个连通块的父节点
    for (int i = 0; i < n * m; i ++ ) f[i] = i;
// 枚举每个位置，如果是黑色格子则检查其上、下、左、右四个位置是否也是黑色格子，如果是则合并
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            if (g[i][j]) {
                if (i && g[i - 1][j]) merge(i * m + j, (i - 1) * m + j);
                if (j && g[i][j - 1]) merge(i * m + j, i * m + j - 1);
            }
        }
    }
    int ans = 0;
    // 枚举每个位置，如果是黑色格子且是它所在连通块的根节点，则答案加1
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            if (g[i][j] && f[i * m + j] == i * m + j) ans ++ ;
        }
    }
    cout << ans << endl;
    return 0;
}