题解 | #玛雅人的密码#

#include <iostream>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
struct code{
    int count;
    string c;
    code(){
        count=0;
        c="";
    }
    code(int a, string b):count(a),c(b){};
};
bool find2012(string x){
    if(x.find("2012")!=string::npos) return true;
    else return false;
}
void swap(string& x,int i,int j){
    char tem=x[i];
    x[i]=x[j];
    x[j]=tem;
}
queue<code> q;
map<string,bool> dic;
void init(){
    while(!q.empty()) q.pop();
    dic.clear();
}
int main(){
    int n;
    while(cin>>n){
        init();
        string x;
        cin>>x;
        code p(0,x);
        q.push(p);
        code tem;
        while(!q.empty()){
            tem=q.front();
            if(find2012(tem.c)) break;
            if(dic[tem.c]) {
            q.pop();
			continue;}
            else{
                dic[tem.c]=true;
                string s=tem.c;
                for(int i=0;i<s.length()-1;i++){
                    swap(s,i,i+1);
                    q.push(code(tem.count+1,s));
                    swap(s,i+1,i);
                }   
                q.pop();

            }
        }
        if(q.empty()) cout<<-1<<endl;
        else cout<<tem.count<<endl;

    }

}