打开转盘锁(100%)

2026-05-05 11:15:38

发布于：浙江

43阅读

0回复

0点赞

//双向BFS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    string e;
    cin >> e;
    unordered_set<string> dead;
    string s;
    while (cin >> s) dead.insert(s);

    // 起点就是目标，直接输出0步
    if (e == "000000") {
        cout << "0" << endl;
        return 0;
    }
    // 目标状态本身是死亡状态，直接不可达
    if (dead.count("000000") || dead.count(e)) {
        cout << "-1" << endl;
        return 0;
    }

    queue<string> q1, q2;
    unordered_map<string, int> d1, d2;

    // 起点方向初始化
    q1.push("000000");
    d1["000000"] = 0;
    // 终点方向初始化
    q2.push(e);
    d2[e] = 0;

    while (!q1.empty() && !q2.empty()) {
        // 每次选择队列较小的一边进行拓展，优化效率
        if (q1.size() <= q2.size()) {
            // 拓展起点方向的一层
            int sz = q1.size();
            for (int i = 0; i < sz; i++) {
                string cur = q1.front();
                q1.pop();
                int step = d1[cur];

                // 对每一位进行+1、-1操作
                for (int j = 0; j < 6; j++) {
                    int digit = cur[j] - '0';
                    // +1操作
                    string nxt = cur;
                    nxt[j] = (digit + 1) % 10 + '0';
                    if (!dead.count(nxt) && !d1.count(nxt)) {
                        if (d2.count(nxt)) {
                            // 碰到终点方向的状态，双向相遇
                            cout << step + d2[nxt] + 1 << endl;
                            return 0;
                        }
                        d1[nxt] = step + 1;
                        q1.push(nxt);
                    }

                    // -1操作（等价于+9再模10）
                    nxt = cur;
                    nxt[j] = (digit + 9) % 10 + '0';
                    if (!dead.count(nxt) && !d1.count(nxt)) {
                        if (d2.count(nxt)) {
                            cout << step + d2[nxt] + 1 << endl;
                            return 0;
                        }
                        d1[nxt] = step + 1;
                        q1.push(nxt);
                    }
                }
            }
        } else {
            // 拓展终点方向的一层
            int sz = q2.size();
            for (int i = 0; i < sz; i++) {
                string cur = q2.front();
                q2.pop();
                int step = d2[cur];

                for (int j = 0; j < 6; j++) {
                    int digit = cur[j] - '0';
                    // +1操作
                    string nxt = cur;
                    nxt[j] = (digit + 1) % 10 + '0';
                    if (!dead.count(nxt) && !d2.count(nxt)) {
                        if (d1.count(nxt)) {
                            cout << step + d1[nxt] + 1 << endl;
                            return 0;
                        }
                        d2[nxt] = step + 1;
                        q2.push(nxt);
                    }

                    // -1操作
                    nxt = cur;
                    nxt[j] = (digit + 9) % 10 + '0';
                    if (!dead.count(nxt) && !d2.count(nxt)) {
                        if (d1.count(nxt)) {
                            cout << step + d1[nxt] + 1 << endl;
                            return 0;
                        }
                        d2[nxt] = step + 1;
                        q2.push(nxt);
                    }
                }
            }
        }
    }

    // 队列空了还没相遇，说明无法到达
    cout << "-1" << endl;
    return 0;
}