题目描述
blablabla
样例
blablabla
算法1
(bfs+kmp) $O(n!*n)$
但是n中只有3个数字2 0 1 且 很多状态重复 所以实际时间复杂度要低得多
C++ 代码
//思路:最小步数模型 + kmp
#include <bits/stdc++.h>
using namespace std;
const int N=13;
int n;
int ne[N];
//kmp匹配2012 如果s中有匹配串则返回true
bool kmp(string s){
//构造next表
string p={"2012"};
ne[0] = -1;
for (int i = 1, j = -1; i <4; i ++ )
{
while (j >= 0 && p[j + 1] != p[i]) j = ne[j];
if (p[j + 1] == p[i]) j ++ ;
ne[i] = j;
}
//匹配
for (int i = 0, j = -1; i < n; i ++ )
{
while (j != -1 && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == 3) return true;
}
return false;
}
int bfs(string str){
queue<string> q;
unordered_map<string,int> d;
q.push(str);
d[str]=0;
int dx[]={-1,1};
while(!q.empty()){
string t=q.front();q.pop();
if(kmp(t)) return d[t];//匹配成功 返回最小步数
int distance=d[t];//由于后面会变换 所以需提前存一下
for(int i=0;i<n;i++){
for(int j=0;j<2;j++){
int a=i+dx[j];
if(a>=0&&a<n){
swap(t[i],t[a]);//变形
if(!d.count(t)){//未遍历过 就遍历
d[t]=distance+1;
q.push(t);
}
swap(t[a],t[i]);//交换回去
}
}
}
}
return -1;
}
int main(){
cin>>n;
string state;cin>>state;
cout<<bfs(state)<<endl;
return 0;
}