【BFS】玛雅人的密码

//用set<string>来代替inq[]和struct中的index了
//就是一开始想到用set了，没啥别的意义
//用node.index和bool inq[maxN]也完全可以
#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;

struct node{
    string str;
    int step;
    node(string s,int st):str(s),step(st){}
};

set<string> inq;    //用来标记字符串是否入过队了，访问过则有inq.find(str)!=inq.end()

void BFS(string origin){
    queue<node> q;
    q.push(node(origin,0));
    inq.insert(origin);
    while(!q.empty()){
        node current = q.front();
        q.pop();
        if(current.str.find("2012")!=string::npos){
            cout<<current.step<<endl;
            return;
        }
        for(int i=0;i<current.str.size()-1;i++){
            string temp = current.str;
            temp[i] = current.str[i+1];
            temp[i+1] = current.str[i];
            if(inq.find(temp)==inq.end()){        //set起到检查temp字符串是否已经入过队了
                q.push(node(temp,current.step+1));
                inq.insert(temp);
            }
        }
    }
    cout<<"-1"<<endl;
}
int main(){
    int N;
    string str;
    while(cin>>N>>str){
        if(N<4)
            cout<<"-1"<<endl;
        else
            BFS(str);
    }
    return 0;
}