题解 | #玛雅人的密码#

玛雅人的密码链接

#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;

struct node{
    int step;
    string str;
    node(int st,string s): step(st),str(s){}
};
set<string> inq;    //用来标记字符串是否入过队了，访问过则有inq.find(str)!=inq.end()
 
void BFS(string origin){
    queue<node> q;
    q.push(node(0,origin));
    inq.insert(origin);
    while(!q.empty()){
        node cur = q.front();
        q.pop();
        if(cur.str.find("2012")!=string::npos){
            cout<<cur.step<<endl;
            return;
            }
        for(int i = 1;i<cur.str.length();i++){
            string s = cur.str;
            char temp = s[i];
            s[i] = s[i-1];
            s[i-1] = temp;
            if(inq.find(s)==inq.end()) {
                q.push(node(cur.step+1,s));
                inq.insert(s);}
        }
    }
    cout<<"-1"<<endl;
}
int main(){
    int N;
    string str;
    while(cin>>N>>str){
        if(N<4)
            cout<<"-1"<<endl;
        else
            BFS(str);
    }
    return 0;
}