题解 | #小红杀怪#

我们可以将问题抽象为一个状态空间搜索问题：

• 状态：用一个二元组 表示两只怪物的当前血量。初始状态为 。
• 目标状态：任何满足 且 的状态。
• 转移：
  1. 火球术 (对怪物 A)：
  2. 火球术 (对怪物 B)：
  3. 烈焰风暴 (群攻)：

由于 的值都很小（），状态空间很小，BFS 是最高效的解法。

我们使用一个队列 queue 来存储待访问的状态，并使用一个 visited 集合来避免重复计算，防止无限循环。

代码

#include <bits/stdc++.h>
using namespace std;

// 使用 tuple<int, int, int> 来存储 (怪物A血量, 怪物B血量, 当前步数)
using State = tuple<int, int, int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, x, y;
    cin >> a >> b >> x >> y;

    queue<State> Q;
    Q.push({a, b, 0});

    array<array<bool, 21>, 21> visited;
    for (auto& row : visited) {
        row.fill(false);
    }

    while (!Q.empty()) {
        auto [ha, hb, step] = Q.front();
        Q.pop();

        // --- 检查目标 ---
        if (ha <= 0 && hb <= 0) {
            cout << step << endl;
            return 0;
        }

        // --- 技能列表 ---
        // 1. 火球术对 A: (ha - x, hb)
        // 2. 火球术对 B: (ha, hb - x)
        // 3. 烈焰风暴: (ha - y, hb - y)

        // 生成所有可能的下一个状态 (na, nb)
        vector<pair<int, int>> next_states = {
            {max(ha - x, 0), hb},
            {ha, max(hb - x, 0)},
            {max(ha - y, 0), max(hb - y, 0)}
        };

        for (const auto& next : next_states) {
            int na = next.first;
            int nb = next.second;

            // 只有未访问过的状态才入队
            if (!visited[na][nb]) {
                visited[na][nb] = true;
                // 入队时将新的步数 step + 1 一起存储
                Q.push({na, nb, step + 1});
            }
        }
    }
    // 如果无法击杀（理论上不可能）
    return 0;
}