题解 | #玛雅人的密码#

//BFS真的很简单
#include <iostream>
#include <queue>
using namespace std;

struct State{
    string str;
    int count;
    State(string str,int count): str(str),count(count){}
};


void BFS(string s,int n)
{
    queue<State> q;
    q.push(State(s,0));
    while(!q.empty())
    {
        State current=q.front();
        q.pop();
        int found=current.str.find("2012");
        if(found!= string::npos)
        {
            cout<<current.count<<endl;
            break;
        }
        for(int i=0;i<n-1;i++)
        {
            State nextstate=current;
            nextstate.count++;
            nextstate.str[i]=current.str[i+1];
            nextstate.str[i+1]=current.str[i];
            q.push(nextstate);
        }
    }
}


int main() {
    int n;
    while (cin >> n) { 
        string s;cin>>s;
        int s2=0,s0=0,s1=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==0+'0')s0++;
            else if(s[i]==1+'0')s1++;
            else s2++;

        }
        if(s2<2||s1<1||s0<1)cout<<"-1"<<endl;
        else{
            BFS(s,n);
        }
    }
}