题解 | 玛雅人的密码

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

using namespace std;

struct NewStr//定义结构体NewStr
{
    string s;//结构体成员s用于存储字符串
    int step;//结构体成员step用于存储步长
    NewStr(int i,string s):step(i),s(s)//结构体构造函数
    {

    }
};

unordered_map<string,bool> isVisited;//创建名为isVisited的哈希表用于存储字符串状态

void BFS(string s)//创建BFS深度优先算法函数
{
    queue<NewStr> q;//创建存储NewStr类型数据的队列
    q.push(NewStr(0,s));//将初始数据压入队列
    isVisited[s]=true;//哈希表记录初始状态为true
    while(!q.empty())//当队列不为空时开始循环
    {
        NewStr first=q.front();//新建NewStr类型str用于接收队首数据
        q.pop();//队首数据出队，同时下一个数据成为队首数据
        string str=first.s;//
        if(str.find("2012")!=string::npos)//若str包含“2012”
        {
            cout<<first.step<<endl;//输出步长
            return;//函数返回
        }
        for(int i=0;i<str.length()-1;i++)//对取出的字符串进行全部的可能性调换演变
        {
            swap(str[i],str[i+1]);//交换
            if(!isVisited[str])//交换完成的字符串如果在哈希表中不为true
            {
                q.push(NewStr(first.step+1,str));//将交换好的字符串压入队列
                isVisited[str]=true;//对应的哈希表变成true
            }
            swap(str[i],str[i+1]);//换回去，以便重新开始新的交换
        }

    }
    cout<<-1<<endl;//若空则返回-1
}
int main() 
{
    int n;
    string s;
    while (cin >> n >> s) { // 注意 while 处理多个 case
        BFS(s);
    }
    return 0;
}