题解 | #玛雅人的密码#

#include <iostream>
#include <map>
#include <queue>
using namespace std;
map<string, bool> visited;
queue<pair<string, int>> q;//队列元素是对组，first是字符串，second是由初始字符串经过多少步所得
pair<string, int> father, child;
string t;
void bfs(string s,int step)
{
	//将爸爸入队
	father.first = s;
	father.second = step;
	q.push(father);
	//只要队列不空
	while (!q.empty())
	{
		//将爸爸出队
		father = q.front();
		q.pop();
		//如果爸爸就是目标字符串，又由于是BFS，其所得步骤一定最少，返回结果即可
		if (father.first.find("2012") != string::npos)
		{
			//队列元素是对组，first是字符串，second是由初始字符串经过多少步所得
			cout << father.second;
			return;
		}
		//如果爸爸没被访问过，就访问，下次遇到就不要入队，避免重复，要保证BFS树每个节点都互异
		if (visited[father.first] == 0)
		{
			visited[father.first] = 1;
			//挨个检查自己的儿子符不符合要求
			for (int i = 0; i < s.length() - 1; i++)
			{
				t = father.first;
				swap(t[i], t[i + 1]);
				if (visited[t]==0)
				{//符合要求的儿子挨个入队
					child.first = t;
					child.second= father.second+1;
					q.push(child);
				}
			}
		}
	}
}
int main()
{
	int N;
	cin >> N;
	string s;
	cin >> s;
	bfs(s,0);
}