两个bug:
1.当输入字符串长度 < 4时,退出
2.当已经找过了某个str,不能重复找,不然会增大距离
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<queue>
using namespace std;
int main(){
int n;
cin>>n;
string str;
cin>>str;
if(str.size() < 4){
cout<<-1<<endl;
return 0;
}
queue<string> q;
unordered_map<string,int> mp;//记录每个字符经过几次变换得来
mp.insert({str,0});
if(str.find("2012") != -1){
cout<<mp[str]<<endl;
return 0;
}
q.push(str);
while(!q.empty()){
string top = q.front(); q.pop();
for(int i = 0;i < top.size() - 1;i++){
string next = top;
char t = next[i];
next[i] = next[i + 1];
next[i + 1] = t;
//如果未被找过,才会找
if(mp.count(next) != 0) continue;
mp[next] = mp[top] + 1;
if(next.find("2012") != -1){
cout<<mp[next]<<endl;
return 0;
}
q.push(next);
}
}
cout<<-1<<endl;
return 0;
}