题解 | 玛雅人的密码(BFS)

#include <algorithm>
#include <any>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_set>
using namespace std;
int n;


int bfs(string str){
    unordered_set<string> strs; //用于记录队列里放了那些元素，避免重复字符串入队，防止没有答案的情况下无限搜索
    queue<string> q;
    q.push(str);
    strs.insert(str);
    while (!q.empty()) {
        string t = q.front();
        q.pop();
        t+="#"; //#号个数记录交换次数
        if(t.find("2012")!=-1){
            int res = t.size()-n-1;
            return res-1;
        }
        for(int i=0;i<n-1;i++){
            swap(t[i],t[i+1]);
            if(strs.find(t.substr(0,n))==strs.end()){ 
                //如果set中不存在，证明该字符串没有在队列里，可以入队
                strs.insert(t.substr(0,n));
                q.push(t);
            }
            swap(t[i],t[i+1]);
        }
    }
    return -1;
}

int main() {
    string str;
    while (scanf("%d", &n) != EOF) {  //记得scanf这里是引用
       cin>>str;
       printf("%d",bfs(str));
    }
}
// 64 位输出请用 printf("%lld")

【代码思路】：宽搜 bfs

【关键点】：

1. 每次出队后、交换前，往字符串后面加个“#”，记录这是第几次交换； 返回时int res = t.size()-n-1; 就是交换次数；
2. 使用一个unorder_set记录队列中放入过那些字符串，防止重复放入；什么时候会重复放入呢？在没有答案的时候，无论交换多少次都无法返回结果，会不断的有重复字符串入队，导致队列永远遍历不完；unorder_set就是防止这个情况的；