牛客 玛雅人的密码

宽搜/字符串变换板子
题

#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;
}