题解 | 玛雅人的密码

思路：采用广度优先遍历，每次从队列头拿出一个字符串，检查，然后生成所有可能的“下一代”字符串放回队列尾部

这样，先入队的（移动步数少的）一定会先被处理，保证了找到的第一个解就是步数最少的解。

存放待处理的字符串——队列；

找子串——find；

记录哪些字符串已经处理过了（防止走回头路，比如从 A 变到 B，又从 B 变回 A）——map；

#include<iostream>
#include<queue>
#include<unordered_map>//时间效率为o(1)，比map高
#include<string>
using namespace std;

//find检查字符串中是否包含子串“2012”
bool contains2012(const string& s) {
    return s.find("2012") != string::npos;
}
//BFS
int bfs(string start, int n) {
    queue<string> q;//存储待访问的字符串
    unordered_map<string, int>
    distMap;//unordered_map存储字符串对应的交换次数，避免重复
    q.push(start);
    distMap[start] = 0;
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int steps = distMap[cur];
        //检查当前状态是否为目标状态
        if (contains2012(cur)) {
            return steps;
        }
        //尝试交换所有相邻的两个字符
        for (int i = 0; i < n - 1; i++) {
            string nextStr = cur;
            swap(nextStr[i], nextStr[i + 1]);
            //如果这个新状态之前没出现过，则入队
            if (distMap.find(nextStr) == distMap.end()) {
                distMap[nextStr] = steps + 1;
                q.push(nextStr);
            }
        }
    }
    return -1;
}
int main() {
    int n;
    string s;
    while (cin >> n >> s) {
        //特殊：若字符串长度小于4，直接输出-1
        if (n < 4) {
            cout << -1 << endl;
            continue;
        }
        //特殊：如果初始字符串就包含2012，输出0
        if (contains2012(s)) {
            cout << 0 << endl;
            continue;
        }
        cout << bfs(s, n) << endl;
    }
    return 0;
}