C++并查集格子游戏

以下是C++实现并查集解决格子游戏的代码和解释：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;
int f[MAXN * MAXN], rank[MAXN * MAXN];
int n, m;

// 初始化并查集
void init() {
    for (int i = 1; i <= n * m; i++) {
        f[i] i;
        rank[i] = 1;
    }
}

// 查找根节点
int find(int x) {
    if (x != f[x]) {
        f[x] = find(f[x]);
    }
    return f[x];
}

// 合并两个集合
void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        if (rank[fx] < rank[fy]) {
            swap(fx, fy);
        }
        f[fy] = fx;
        rank[fx] += rank[fy];
    }
}

int main() {
    cin >> n >> m;
    init();
    vector<vector<int>> grid(n, vector<int>(m));
    // 输入格子游戏的矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    // 遍历矩阵，合并相邻的格子
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0 && grid[i][j] == grid[i - 1][j]) {
                merge((i - 1) * m + j + 1, i * m + j + 1);
            }
            if (j > 0 && grid[i][j] == grid[i][j - 1]) {
                merge(i * m + j, i * m + j + 1);
            }
        }
    }
    // 统计不同集合的个数
    int cnt = 0;
    for (int i = 1; i <= n * m; i++) {
        if (f[i] == i) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

解释：

首先，我们需要定义一个并查集，用于维护格子之间的连通性。在这个并查集中，每个格子都是一个节点，如果两个格子相邻且颜色相同，则它们属于同一个集合。我们可以使用一个二维数组来表示格子游戏的矩阵，其中每个元素表示该位置的格子颜色。

接下来，我们需要遍历整个矩阵，对于每个格子，如果它和它上面或左边的格子颜色相同，则将它们合并到同一个集合中。这里我们使用路径压缩和按秩合并两种优化方式，可以提高查询效率。

最后，我们统计不同集合的个数，即为最终答案。