玛雅人的密码

思路

将原始字符串看作树的根节点，进行一次交换的字符串作为子节点，依次往下交换，然后使用广度优先搜索（BFS）遍历这棵树，也就是层序遍历，每层的字符串对应一个 Map 值，含有2012的字符串在哪一层，就输出该层的 Map 值，如图所示。保证树上的每个结点都不相同，直到穷尽。

#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>

using namespace std;

struct NewStr{
    string s;
    int step;
    NewStr(int i, string s):step(i), s(s){}
};

unordered_map<string, bool> isVisited;//避免重复入队相同字符串
void bfs(string s){
    queue<NewStr> q;
    q.push(NewStr(0, s));
    isVisited[s] = true;
    while(!q.empty()){
        NewStr t = q.front();
        q.pop();
        string ts = t.s;
        if(ts.find("2012") != string::npos){
            cout << t.step << endl;
            return;
        }
        for(int i = 0; i < ts.size() - 1; i ++){
            swap(ts[i], ts[i + 1]);
            if(!isVisited[ts]) {
                q.push(NewStr(t.step + 1, ts));
                isVisited[ts] = true;
            }
            swap(ts[i], ts[i + 1]);
        }
    }
    cout << -1 << endl;
} 

int main(){
    int n;
    string s;
    while(cin>>n>>s){
        bfs(s);
    }
    return 0;
}