题解 | #密码锁#

BFS广搜即可

代码：

#include<iostream>
#include<set>
#include<queue>
using namespace std;
int n;
//检查是否含有2012
int check(string& s){
    for(int i=0;i<=n-4;++i) if(s.substr(i,4)=="2012") return 1;
    return 0;
}
//相邻位置交换
void change(string& s,set<string>&ss,queue<string>& q){
    char tp;
    for(int i=1;i<n;++i){
        string t(s);
        tp=t[i],t[i]=t[i-1],t[i-1]=tp;
        if(!ss.count(t)) ss.emplace(t),q.emplace(t);
    }
}
int main(){
    ios::sync_with_stdio(false);
    string str;
    while(cin>>n){
        cin>>str;
        int a[3]={0,0,0};
        for(int i=0;i<n;++i) a[str[i]-'0']++;
        //不可能出现2012
        if(!a[0]||!a[1]||a[2]<2){
            cout<<-1<<endl;
            continue;
        }
        queue<string>q;
        set<string>s;
        q.emplace(str);
        s.emplace(str);
        int cnt=0;
        string t;
        //BFS扩展
        while(!q.empty()){
            int len=q.size();
            bool f=false;
            for(int i=0;i<len;++i){
                t=q.front();  q.pop();
                if(check(t)){
                    f=true; break;
                } 
                change(t,s,q);
            }
            if(f){
                cout<<cnt<<endl;
                break;
            }
            ++cnt;
        }
    }
    return 0;
}