题解思路

该问题可以通过广度优先搜索（BFS）来解决。我们需要找到巫师打开最少的箱子以获取“魔法石”的最短路径。每个箱子需要特定的魔法石才能打开，打开后可以获得新的魔法石。状态转移的关键在于每次打开一个箱子后，新的魔法石会被加入当前集合，从而可能解锁更多箱子。

​​1.输入处理与映射​​：将每个魔法石名称映射到唯一的ID，便于使用位掩码快速处理。

​​2.BFS初始化​​：初始状态为巫师已有的魔法石集合。

​​3.状态转移​​：对于每个状态，遍历所有未打开的箱子，检查是否满足开启条件。若满足，则生成新状态并加入队列。

4.终止条件​​：当新状态包含目标魔法石时，返回当前开启的箱子数目。

代码实现

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
#include <unordered_set>
#include <bitset>
using namespace std;

struct Chest {
    bitset<2000> required;
    int result_id;
};

int main() {
    int N, M;
    while (cin >> N >> M) {
        if (N == 0 && M == 0) break;
        cin.ignore(); // 忽略换行符

        unordered_map<string, int> name_to_id;
        int id_counter = 0;
        bitset<2000> initial_bits;

        // 读取初始石头
        for (int i = 0; i < N; ++i) {
            string name;
            getline(cin, name);
            if (!name_to_id.count(name)) {
                name_to_id[name] = id_counter++;
            }
            initial_bits.set(name_to_id[name]);
        }

        vector<Chest> chests;
        // 读取箱子
        for (int i = 0; i < M; ++i) {
            string line;
            getline(cin, line);
            size_t colon_pos = line.find(':');
            string required_part = line.substr(0, colon_pos);
            string result_part = line.substr(colon_pos + 2);

            // 处理结果石
            string r_name = result_part;
            if (!name_to_id.count(r_name)) {
                name_to_id[r_name] = id_counter++;
            }
            int r_id = name_to_id[r_name];

            // 处理需求石
            vector<string> required_names;
            size_t pos = 0;
            while (true) {
                size_t comma_pos = required_part.find(", ", pos);
                if (comma_pos == string::npos) {
                    required_names.push_back(required_part.substr(pos));
                    break;
                } else {
                    required_names.push_back(required_part.substr(pos, comma_pos - pos));
                    pos = comma_pos + 2;
                }
            }

            bitset<2000> req_bits;
            for (const string& name : required_names) {
                if (!name_to_id.count(name)) {
                    name_to_id[name] = id_counter++;
                }
                req_bits.set(name_to_id[name]);
            }
            chests.push_back({req_bits, r_id});
        }

        // 检查目标是否存在
        string target_name = "Sorcerer's Stone";
        if (!name_to_id.count(target_name)) {
            cout << -1 << endl;
            continue;
        }
        int target_id = name_to_id[target_name];

        if (initial_bits.test(target_id)) {
            cout << 0 << endl;
            continue;
        }

        // BFS
        queue<pair<bitset<2000>, int>> q;
        unordered_set<string> visited;
        q.push({initial_bits, 0});
        visited.insert(initial_bits.to_string());

        bool found = false;
        while (!q.empty()) {
            auto [current_bits, steps] = q.front();
            q.pop();

            for (const Chest& chest : chests) {
                if (current_bits.test(chest.result_id)) continue;
                if ((current_bits & chest.required) != chest.required) continue;

                bitset<2000> new_bits = current_bits;
                new_bits.set(chest.result_id);
                if (new_bits.test(target_id)) {
                    cout << steps + 1 << endl;
                    found = true;
                    goto end;
                }

                string key = new_bits.to_string();
                if (!visited.count(key)) {
                    visited.insert(key);
                    q.push({new_bits, steps + 1});
                }
            }
        }
        end:
        if (!found) cout << -1 << endl;
    }
    return 0;
}