#广度优先遍历应用#玛雅人的密码#清华大学机试

https://www.acwing.com/problem/content/3388/

思路：本题难点在于，如何确保所有可能的子序列都被遍历到，还要保证不能重复遍历。相比于深度优先，广度优先一层一层来的思想更好的保证了这一基本原则，把每一经过旋转的子序列看作是下一层，同时维护一个数据结构记录是否被访问即可

解法

1.读入数据，若数据小于4直接返回-1；若大于，则维护一个无序map记录是否被访问，一个辅助队列进行广度优先遍历，一个cur字符串记录当前的子序列。将原始字符串压入栈中

2.当栈不为空时，先弹出栈顶字符串检查是否有2012，语法采用cur.find("2012" )!= string::npos,如有则输出对应的distance值并退出执行，如没有则继续

3.从0到cur.size()-1遍历字符串，挨个进行交换：如果在map里面没有找到对应的字符串next，则证明未被访问过。将该节点的键值对插入maps，值设置为cur的distance值+1；

4.循环结束，如果栈为空，直接打印-1

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    char strarr[20] = {0};
    scanf("%d", &n);
    scanf("%s", strarr);
    if (n < 4) {
        printf("-1\n");
        return 0;
    }

    string str = strarr;
    queue<string> toVisit;
    unordered_map<string, int> distance;
    distance.insert({str, 0});
    toVisit.push(str);
    while (!toVisit.empty()) {
        string cur = toVisit.front();
        if (cur.find("2012") != string ::npos) {
            printf("%d\n", distance[cur]);
            break;
        }
        toVisit.pop();

        for (int i = 0; i < cur.size() - 1; i++) {
            string next = cur;//next负责记录两元素翻转之后的下一个字符串
            char tmp = next[i];
            next[i] = next[i + 1];
            next[i + 1] = tmp;//完成交换
            if(distance.count(next) == 0){
                toVisit.push(next);
                distance.insert({next,distance[cur]+1});
            }

        }

    }
    if(toVisit.empty()){
        printf("-1\n");
    }
    return 0;
}