题解 | #玛雅人的密码#

BFS搜索，为了保证算法能停下来要设置visit数组保存遍历过的顺序。
用结构体记录现在的顺序以及交换过多少次。

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
using namespace std;

struct code{
    string str;
    int time;
    code(){}
    code(string s,int t):str(s),time(t) {}
};

vector<string> visit;

int find(vector<string> visit,code c){
    for(int i=0;i<visit.size();i++)
        if(c.str==visit[i])
            return i;
    return -1;
}

int BFS(code c){
    int count=0;
    queue<code> q;
    q.push(c);
    while(!q.empty()){
        if(find(visit,q.front())!=-1){
            q.pop();
            continue;
        }
        if(q.front().str.find("2012")!=-1)
            return q.front().time;
        else{
            code current=q.front();
            visit.push_back(current.str);
            q.pop();
            for(int i=0;i<current.str.size()-1;i++){
                code temp=current;
                swap(temp.str[i],temp.str[i+1]);
                temp.time++;
                q.push(temp);
            }
        }
    }
    return -1;
}

int main(){
    int n;
    string str;
    while(cin>>n){
        cin>>str;
        visit.clear();
        code c(str,0);
        cout<<BFS(c)<<endl;
    }
}