宽搜/字符串变换板子
题
#include<bits/stdc++.h>
using namespace std;
struct Node{
string s;
int st;
Node(string ss, int x):s(ss), st(x){};
};
int n;
unordered_map<string, int>vis; //避免重复字符串入队
void bfs(string ss){ //宽搜没有递归调用这一过程
queue<Node>q;
q.push(Node(ss, 0));
vis[ss] = 1; //记录该字符串已经搜索过
while(q.size()){
Node t = q.front();
string sw = t.s;
q.pop();
vis[sw] = true;
if(sw.find("2012") != string::npos){
cout<<t.st<<endl;
return ;
}
for(int i = 0; i < sw.length() - 1; i ++ ){
swap(sw[i], sw[i + 1]);
if(!vis[sw]){
q.push(Node(sw, t.st + 1));
vis[sw] = true;
}
swap(sw[i], sw[i + 1]);
}
}
cout<<-1<<endl;
}
int main()
{
string str;
while(cin>>n>>str){
bfs(str);
}
return 0;
}