简单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']++;
if(!a[0]||!a[1]||!a[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;
}