并查集在蜂窝网格游戏算法中的应用与实践

1. 题目背景与核心思路解析

2021年浙江省大学生程序设计竞赛（ZJCPC）的G题"Wall Game"是一道典型的并查集应用与思维结合的算法题。题目设定在一个蜂窝网格中，两位玩家轮流建造墙壁，目标是将对方的基地完全包围。这种类型的题目在ICPC/CCPC等编程竞赛中非常典型，考察选手对基础数据结构的灵活运用和问题抽象能力。

1.1 蜂窝网格的数学建模

蜂窝网格可以看作是由六边形组成的无限平面，每个六边形单元有六个相邻单元。在编程实现中，我们通常用坐标系来表示这些单元。常见的有两种坐标系表示方法：

1. 轴向坐标系(Axial Coordinates)：使用两个坐标轴(q,r)表示
2. 偏移坐标系(Offset Coordinates)：将网格视为"错位"的矩形网格

以轴向坐标系为例，每个六边形单元可以表示为(q,r)，其六个相邻单元为：

• (q+1, r)
• (q-1, r)
• (q, r+1)
• (q, r-1)
• (q+1, r-1)
• (q-1, r+1)

1.2 并查集的核心作用

并查集(Disjoint Set Union, DSU)是解决这道题的关键数据结构，主要用于：

1. 动态维护蜂窝单元的连通性
2. 快速判断两个单元是否属于同一连通区域
3. 检测是否形成了完全包围的闭环

并查集在此题中的特殊之处在于需要处理蜂窝网格的特殊邻接关系，以及判断包围状态的算法设计。

2. 算法设计与实现细节

2.1 并查集的扩展实现

标准的并查集需要做以下扩展以适应题目需求：

cpp复制struct DSU {
    vector<int> parent;
    vector<int> size;
    
    DSU(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for(int i=0; i<n; i++) parent[i] = i;
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(size[x] < size[y]) swap(x, y);
        parent[y] = x;
        size[x] += size[y];
        return true;
    }
};

2.2 包围检测的关键算法

判断是否形成包围是本题最核心的思维点。可以采用以下方法：

1. 虚拟边界法：在网格外围设置一圈虚拟边界点
2. 连通性检测：每次放置新墙后，检查玩家区域是否与虚拟边界连通
3. 包围判定：如果玩家区域不与任何虚拟边界连通，则说明被完全包围

具体实现时，可以为每个玩家维护两个并查集：

• 一个用于正常游戏单元
• 一个包含虚拟边界单元

2.3 坐标映射与哈希处理

由于蜂窝网格可能是无限的，需要将二维坐标映射为一维索引：

cpp复制struct Point {
    int q, r;
    bool operator<(const Point& other) const {
        return tie(q, r) < tie(other.q, other.r);
    }
};

map<Point, int> point_to_id;
int current_id = 0;

int get_id(Point p) {
    if(!point_to_id.count(p)) {
        point_to_id[p] = current_id++;
    }
    return point_to_id[p];
}

3. 完整解题流程与代码实现

3.1 输入处理与初始化

cpp复制int main() {
    int n;
    cin >> n;
    
    // 为两个玩家各准备一个并查集
    DSU player1(n * 2 + 2), player2(n * 2 + 2);
    
    // 虚拟边界节点的ID
    const int BOUNDARY1 = n * 2;
    const int BOUNDARY2 = n * 2 + 1;
    
    map<Point, int> cells;
    int id_counter = 0;
    
    while(n--) {
        int player, q, r;
        cin >> player >> q >> r;
        Point current{q, r};
        
        // 获取或分配当前单元格ID
        if(!cells.count(current)) {
            cells[current] = id_counter++;
        }
        int current_id = cells[current];
        
        DSU& dsu = (player == 1) ? player1 : player2;
        int boundary = (player == 1) ? BOUNDARY1 : BOUNDARY2;
        
        // 检查六个方向
        vector<Point> neighbors = {
            {q+1, r}, {q-1, r},
            {q, r+1}, {q, r-1},
            {q+1, r-1}, {q-1, r+1}
        };
        
        bool surrounded = true;
        for(auto& neighbor : neighbors) {
            if(cells.count(neighbor)) {
                int neighbor_id = cells[neighbor];
                dsu.unite(current_id, neighbor_id);
            } else {
                // 未建造的邻居视为边界
                surrounded = false;
            }
        }
        
        // 检查是否与虚拟边界连通
        if(dsu.find(current_id) == dsu.find(boundary)) {
            surrounded = false;
        }
        
        if(surrounded) {
            cout << (player == 1 ? 2 : 1) << " wins at move " << (n_total - n) << endl;
            return 0;
        }
    }
    
    cout << "Draw" << endl;
    return 0;
}

3.2 算法优化与性能分析

1. 路径压缩与按秩合并：确保并查集操作接近O(1)
2. 坐标哈希：使用map存储坐标到ID的映射，查找O(log n)
3. 空间优化：动态分配ID，避免预先分配过大空间

时间复杂度：O(n α(n))，其中α是反阿克曼函数
空间复杂度：O(n)

4. 竞赛技巧与注意事项

4.1 调试与验证技巧

1. 小规模测试用例：手工构造简单蜂窝网格验证基础逻辑

   • 例如3个单元格形成的三角形包围
   • 直线型排列的单元格

2. 边界情况测试：

   • 第一个回合就形成包围
   • 最后一个回合才形成包围
   • 永远无法形成包围的情况

3. 可视化调试：可以打印出网格状态辅助调试

cpp复制void print_grid(const map<Point, int>& cells) {
    // 找出q和r的范围
    int min_q = INT_MAX, max_q = INT_MIN;
    int min_r = INT_MAX, max_r = INT_MIN;
    for(auto& [p, id] : cells) {
        min_q = min(min_q, p.q);
        max_q = max(max_q, p.q);
        min_r = min(min_r, p.r);
        max_r = max(max_r, p.r);
    }
    
    // 打印网格
    for(int r = max_r; r >= min_r; r--) {
        // 缩进对齐六边形网格
        if((max_r - r) % 2 == 1) cout << "  ";
        
        for(int q = min_q; q <= max_q; q++) {
            if(cells.count({q, r})) {
                cout << "X ";
            } else {
                cout << ". ";
            }
        }
        cout << endl;
    }
}

4.2 常见错误与陷阱

1. 坐标系统错误：混淆q和r的方向或偏移量

   • 确保六个方向的邻居计算正确
   • 可以在纸上画出坐标系验证

2. 包围判断逻辑不完整：

   • 忘记考虑虚拟边界的情况
   • 没有正确处理多个独立区域的情况

3. 性能问题：

   • 使用非优化的并查集实现导致超时
   • 不必要的重复计算

4. 初始化错误：

   • 忘记初始化并查集的parent数组
   • 虚拟边界节点ID冲突

4.3 竞赛策略建议

1. 先实现基础版本：确保正确性优先
2. 添加详细注释：方便调试和检查
3. 准备测试用例：包括极端情况和小规模案例
4. 时间管理：如果卡住，可以先标记后回头再看

5. 算法扩展与变种思考

5.1 题目变种与解法调整

1. 可变玩家数量：扩展到3个或更多玩家

   • 需要为每个玩家维护独立的并查集
   • 胜利条件可能变为最后一个未被包围的玩家

2. 不同网格类型：方形网格、三角形网格等

   • 需要调整邻居计算方式
   • 包围判断逻辑可能不同

3. 动态拆除墙壁：允许玩家拆除已有墙壁

   • 需要支持并查集的"拆开"操作
   • 可以使用支持撤销操作的并查集实现

5.2 实际应用场景

这种类型的算法可以应用于：

1. 游戏AI开发：六边形棋盘类游戏的智能判断
2. 地理信息系统：区域划分与连通性分析
3. 材料科学：分子结构的包围与包裹分析

5.3 进一步学习方向

1. 高级并查集应用：

   • 带权并查集
   • 可持久化并查集
   • 支持动态连接的并查集

2. 计算几何：

   • 更复杂的网格系统分析
   • 三维蜂窝结构的处理

3. 博弈论：

   • 玩家策略分析
   • 必胜策略研究