题解 | #玛雅人的密码#

//BFS宽度优先搜索
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

struct strtype{
    string value;
    int num;
    strtype(string s,int n):value(s),num(n){}
};
queue<strtype> myqueue;
map<string ,bool> mymap;
int BFS(int n){
    while(!myqueue.empty()){
        strtype current=myqueue.front();
        myqueue.pop();
        //如果当前值匹配2012，返回其对应的交换次数
        if(current.value.find("2012")!=string::npos){
            return current.num;
        }
        //未匹配，就把新一轮交换的放进队列里
        string str=current.value;
        int num=current.num;
        string temp;
        for(int i=0;i<n-1;i++){
            temp=str;
            char c=temp[i];
            temp[i]=temp[i+1];
            temp[i+1]=c;
            if(mymap.find(temp)!=mymap.end()){//如果已经匹配过这个字符串了
                continue;
            }
            else{//未匹配过的就标记一下，并且放进队列里
                mymap[temp]=true;
                myqueue.push(strtype(temp,num+1));
            }
        }
    }
    return -1;
}
int main() {
    int n;
    while(cin>>n){
        mymap.clear();
        myqueue=queue<strtype>();
        string str;
        cin>>str;
        myqueue.push(strtype(str,0));
        mymap[str]=true;
        cout<<BFS(n)<<endl;
    }
    return 0;
}