题解 | #玛雅人的密码#

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;

string Swap(string str,int i)
{
	swap(str[i],str[i + 1]);
	return str;
}

int main(void)
{
	int len;
	string str;
	cin >> len >> str;
	int ans = -1;
	if(str.find("2012") != -1){
		ans = 0;
		cout << ans << endl;
		return 0;
	}
	
	//进行BFS
	queue<string>q;
	unordered_map<string,int>mp;
	q.push(str);
	mp[str] = 0;
	while(!q.empty())
	{
		bool f = false;
		string tmp = q.front();
		q.pop();
		for(int i = 0;i < len - 1;i++)
		{
			string newS = Swap(tmp,i);
			if(newS.find("2012") != -1) {
				ans = mp[tmp] + 1;
				f = true;
				break;
			}
			if(mp.count(newS) == 0){
				mp[newS] = mp[tmp] + 1;
				q.push(newS);
			}
		}
		if(f)break;
	}
	cout << ans << endl;
	return 0;
}