题解 | #玛雅人的密码#

广度优先搜索，通过搜索状态结构体记录每一层的移动次数

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct status {
    string code;
    int moveTime;
    status(string s, int i) {
        code = s;
        moveTime = i;
    }
};
int main() {
    int n;
    string s;
    while (cin >> n >> s) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        queue<status> myQueue;
        unordered_map<string, bool> myMap;
        int searchTime = -1;
        myQueue.push(status(s, 0));
        myMap.insert(make_pair(s, true));
        while (!myQueue.empty()) {
            status current = myQueue.front();
            myQueue.pop();
            if (current.code.find("2012") != string::npos) {
                searchTime = current.moveTime;
                break;
            }
            for (int i=0;i <= current.code.size() - 2; i++) {
                string temp = current.code;
                swap(temp[i], temp[i + 1]);
                if (myMap.find(temp) == myMap.end()) {
                    myMap[temp] = true;
                    myQueue.push(status(temp, current.moveTime + 1));
                }
            }

        }
        cout<<searchTime<<endl;
    }
}
// 64 位输出请用 printf("%lld")