题解 | #玛雅人的密码#

//采用广度优先遍历
#include "stdio.h"
#include "string"
#include "queue"
#include "map"
using namespace std;
struct TreeNode{
    string code;
    int sum;
};

int BFS_CODE(string str){
    queue<TreeNode> myQueue;//用于广度优先遍历
    map<string,bool> myMap;//用于识别字符串相同的TreeNode
    TreeNode node;
    node.code = str;
    node.sum = 0;
    myQueue.push(node);
    myMap[str] = true;
    while (!myQueue.empty()){
        TreeNode node2 = myQueue.front();
        myQueue.pop();
        string code = node2.code;int sum = node2.sum;
        int count = node2.code.find("2012");
        if (count != string::npos)
            return node2.sum;
        for (int i = 0; i < node2.code.size()-1; ++i) {
            swap(node2.code[i],node2.code[i+1]);
            node2.sum++;
            map<string,bool> ::iterator it = myMap.find(node2.code);
            if (it != myMap.end()){//map中已有此字符串
                swap(node2.code[i],node2.code[i+1]);//此处再交换是不让node2中的code改变
                node2.sum--;
                continue;
            }
            else{
                myQueue.push(node2);
                myMap[node2.code] = true;
                swap(node2.code[i],node2.code[i+1]);//与上面的再交换同理
                node2.sum--;
            }
        }
    }
    return -1;
}

int main(){
    int N;char buf[14]={};
    while (scanf("%d",&N)!=EOF){
        getchar();
        for (int i = 0; i < N; ++i) {
            scanf("%c",buf+i);
        }
        string str = buf;
        printf("%d\n", BFS_CODE(str));
    }
}