玛雅人的秘密---广搜

题目

玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。

思路

参考了牛客大神的做法，感觉很巧妙，加深了对广搜的认识。
从初始字符串序列开始广搜，每次搜索就等同于对当前字符串进行一次移位。使用map记录当前字符串是经过多少次移位得到的，每次移位后判断是否满足2012的要求，满足的话之间打印map[curstr]的结果就好。广搜遍历完所有移位情况后，如果还没找到满足要求的字符串，则返回-1。

代码

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

map<string, int> mp; // 记录某个字符串从初始字符串经交换的次数
queue<string> Q;

string swapChar(string str, int i)
{
    string newStr = str;
    char tmp = newStr[i];
    newStr[i] = newStr[i+1];
    newStr[i+1] = tmp;
    return newStr;
}

bool judge(string str)
{
    if(str.find("2012", 0) == string::npos) return false;
    else return true;
}

int bfs(string str)
{
    string newStr;
    mp.clear();
    while(!Q.empty()) Q.pop(); // 清空队列
    Q.push(str); // 压入初始的字符串
    mp[str] = 0; // 初始字符串经交换的次数为0
    while(!Q.empty()) {
        str = Q.front();
        Q.pop();
        for(int i = 0; i < str.size()-1; i++) {
            newStr = swapChar(str, i);
            if(mp.find(newStr) == mp.end()) { // 看newStr是否已经出现过了；未出现过
                mp[newStr] = mp[str] + 1;
                if(judge(newStr) == true) { // 看交换过的此字符串是否满足2012要求
                    return mp[newStr];
                }
                else Q.push(newStr);
            }
            else continue;
        }
    }
    return -1; // 遍历了所有情况，未找到符合要求的情况
}

int main()
{
    int n;
    string str;
    while(cin >> n) {
        cin >> str;
        if(judge(str) == true) cout << 0 << endl;
        else {
            int ans = bfs(str);
            cout << ans << endl;
        }
    }
    return 0;
}