题解 | 玛雅人的密码

#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct zu{
    string st;
    int count;//交换次数和交换后的字符串打包
};
queue<zu> q;//队列存放每个打包内容
void swap(char &a,char &b)
{
    char temp=a;
    a=b;
    b=temp;
}
bool find2012(string &s){
    for(int i=0;i<=s.size()-4;i++)
    {
        if(s[i]=='2'&&s[i+1]=='0'&&s[i+2]=='1'&&s[i+3]=='2')
        return true;
    }
    return false;
}
void bfs(string &n,int s)
{
    int count=0;
    zu z_current,z_temp;
    while(!q.empty())
    {
        z_current=q.front();
        q.pop();
        //如果能找到2012
        if(find2012(z_current.st))
        {cout<<z_current.count;
        return;}
        else {
        //没找到2013就交换一次字符串，并保留所有结果到队中
        for(int i=0;i<s-1;i++)//遍历你输入的字符串
        {
            swap(z_current.st[i],z_current.st[i+1]);
            z_temp.st=z_current.st;
            z_temp.count=z_current.count+1;
            q.push(z_temp);
            swap(z_current.st[i],z_current.st[i+1]);//再换回来进行下一个交换
        }
        }
    }
    cout<<-1<<endl;
}
int main() {
    int n;
    string str;
    cin>>n>>str;
    zu z;
    z.st=str;
    z.count=0;
    q.push(z);
    bfs(str,n);
    return 0;
}
// 64 位输出请用 printf("%lld")