题解 | #玛雅人的密码#

利用map来实现对以访问字符串的标记
#include<iostream>
#include<map>
#include<queue>
using namespace std;

struct miya {
	string str;
	int num;
};


void BFS(string str) {

	map<string, bool> isvisited;  //保存以及访问过的结点
	queue<miya> myqueue;
	miya prime;
	prime.num = 0; prime.str = str;

	myqueue.push(prime);  //初始结点入栈
	isvisited[prime.str] = true;

	while (!myqueue.empty()) {
		miya cur = myqueue.front();
		myqueue.pop();  //弹出队首元素
		if (cur.str.find("2012") != string::npos) {
			cout << cur.num << endl;
			return;
		}
		for (int i = 1; i < cur.str.size(); i++) {
			char temp;
			miya neighber = cur;
			temp = neighber.str[i];
			neighber.str[i] = neighber.str[i - 1];
			neighber.str[i - 1] = temp;   //完成字符位移
			neighber.num++;

			if (isvisited.find(neighber.str) == isvisited.end())
			{
				isvisited[neighber.str] = true;
				myqueue.push(neighber);  //将未访问结点入栈
			}
			else continue;
		}
	}

}

int main()
{
	//使用广度优先搜索来实现
	int n;
	string str;
	
	while (cin >> n) {
		cin >> str;
		BFS(str);

	}

}