题解 | 玛雅人的密码

#include <bits/stdc++.h>
using namespace std;

struct sc{
    string s;
    int c;
    int count;//c记录坐标，防止出现回溯
    sc(string s,int c,int count):s(s),c(c),count(count){}
};

int find2012(string s){
    for(int i=0;i<s.size()-3;i++){
        if(s[i]=='2'&&s[i+1]=='0'&s[i+2]=='1'&&s[i+3]=='2')return 1;
    }
    return 0;
}

void swap(string &s,int i,int j){
    char c=s[i];
    s[i]=s[j];
    s[j]=c;
}

int BFS(string s){
    std::queue<sc> q;
    q.push(sc(s,-1,0));
    while(!q.empty()){
        sc x=q.front();
        q.pop();
        if(find2012(x.s)==1)return x.count;
        for(int i=0;i<s.size()-1;i++){
            if(i==x.c)continue;
            string t=x.s;
            swap(t,i,i+1);
            q.push(sc(t,i,x.count+1));
        }
    }
    return -1;
}

int main(){
    int n;
    string s;
    while(cin>>n>>s){
        if(BFS(s)==0){
            if(find2012(s)==0)cout<<-1<<endl;
            else cout<<0<<endl;
        }else cout<<BFS(s)<<endl;
    }
}

这题主要分享一下BFS的思路，BFS本质上就是一种规则化搜索，也就是特殊的遍历，那么，我们针对这个问题，就很容易分析了，这里需要找到密码，遍历规则是交换相邻的元素，那么根据遍历的基本要求，遍历是不能重复的，那么我们使用一个结构体记录遍历中该变动字符的变化次数和上次变化位置即可，只要下次不在这个位置变化， 就一定是新的字符串，然后就可以利用queue完成一次全可能性的搜索，就得到了结果