「PA 2018」Gra 题解

问题分析

这是一个策略游戏模拟问题，需要在网格地图上协调农民收集金币和坦克清除石头，最终将所有金币运回基地。

游戏规则：

• 地图：$n \times n$ 网格，基地位于 $(0,0)$
• 角色：农民（收集金币，不能进入有石头的格子）、坦克（清除石头，可进入任何格子）
• 经济：初始 200 金币，招募角色各需 100 金币
• 移动：每轮每个角色最多移动一次
• 收集：农民每轮最多收集 10 金币，坦克每轮最多清除 10 石头

代码算法解析

核心架构：启发式搜索 + 贪心策略

主要组件：

1. 路径规划系统（模板类 C1-C6）
2. 角色管理系统（Unit 结构体）
3. 决策引擎（next_move 函数）
4. 多轮优化（game 函数中的重试机制）

路径规划算法

代码实现了 6 种不同的路径规划策略：

// C1: 寻找最近的金币堆
struct C1 {
    static float dist(int, int, int, int) { return 1 + random1() / 100000; }
    static int score(int a, int b, float) { return map[a][b] > 0; }
    static bool end(int a, int b) { return map[a][b] > 0; }
    static bool walkable(int a, int b) { return map[a][b] >= 0 && units[a][b].type == Unit::None; }
};

其他路径策略：

• C2: 寻找价值最高的金币堆
• C3: 寻路到指定坐标
• C4: 寻找空闲农民
• C5: 寻找最佳石头清除目标
• C6: 寻找最近的非金币格子

决策逻辑

角色招募策略：

if (stone_prob == 0) {
    recruit(1);  // 无石头时直接招募农民
} else if (number_of_units == 0) {
    // 第一个角色：如果旁边有金币就招农民，否则招坦克
    if (map[1][0] > 0 || map[0][1] > 0) recruit(1);
    else recruit(0);
} else if (number_of_units == 1) {
    // 第二个角色：平衡农民和坦克数量
    if (number_of_tanks == 0) recruit(0);
    else recruit(1);
}

农民移动策略：

• 优先收集高价值金币
• 背包金币达到阈值时返回基地
• 使用 dir_to_best_gold_pile 和 dir_to_nearest_gold_pile

坦克移动策略：

• 优先清除阻挡路径的石头
• 使用 dir_to_best_stone 寻找最佳目标
• 空闲时移动到边缘区域

优化技术

1. 随机化：在距离计算中加入随机因子，避免陷入局部最优
2. 限制搜索深度：使用 limit 参数控制路径搜索范围
3. 动态角色数量限制：根据石头概率调整最大角色数
4. 多轮重试：对每个测试用例进行多次尝试，选择最优解

算法流程

void game(int number, int limit) {
    do {
        // 初始化游戏状态
        initialize_game();
        
        // 游戏主循环
        while (next_turn() && turn < limit) {
            // 每轮决策
        }
        
        // 记录最优解
        if (turn < best_score) {
            best_score = turn;
            best_solution = current_solution;
        }
    } while (未找到可行解);
}

复杂度分析

• 时间复杂度：$O(T \cdot \text{attempts} \cdot n^2 \cdot \text{turns})$
• 空间复杂度：$O(n^2)$
• 路径搜索：使用优先队列的 BFS，$O(n^2 \log n)$

关键优化点

1. 启发式评估函数：综合考虑距离、金币价值、石头数量
2. 角色协同：农民和坦克的移动策略相互配合
3. 经济管理：合理分配金币招募角色
4. 轮次优化：在限制轮数内完成目标

算法标签

• 启发式搜索
• 贪心算法
• 状态空间搜索
• BFS

总结

这个解法展示了在复杂约束下的智能体协同控制问题：

1. 通过多种路径规划策略适应不同场景
2. 使用启发式函数平衡探索与利用
3. 实现农民与坦克的有效分工协作
4. 在严格轮数限制下找到可行解

该算法结合了搜索、规划、优化等多种技术，是解决此类策略游戏问题的典型范例。