题解 | #玛雅人的密码#

广度优先搜索，用了unordered_map标记字符串是否已经被访问过

#include <iostream>
#include <queue>
#include "queue"
#include "unordered_map"
using namespace std;
struct status {
    string code;
    int count;
    status(string s, int a) {
        code = s;
        count = a;
    }
};
int bfs(string code){
        queue<status> countQueue;
        unordered_map<string,bool> visitMap;
        countQueue.push(status(code, 0));
        visitMap[code]=true;
        while (!countQueue.empty()) {
            status current = countQueue.front();
            countQueue.pop();
            if (current.code.find("2012") != string::npos) {
                return current.count;
            }
            for(int i=0;i<=code.size()-2;i++){
                string temp=current.code;
                swap(temp[i],temp[i+1]);
                if(visitMap[temp]) continue;
                countQueue.push(status(temp,current.count+1));
                visitMap[temp]=true;
            }
        }
        return -1;
}
int main() {
    int n;
    string code;
    while (cin >> n >> code) { // 注意 while 处理多个 case
        cout << bfs(code)<< endl;
        
    }
}
// 64 位输出请用 printf("%lld")