题解 | #玛雅人的密码# bfs + un_map

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

int n;
string s;

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

unordered_map<string, bool> isvisit;
void bfs(string s)
{
    queue<New_String> q;
    q.push(New_String(0, s));
    isvisit[s] = true;
    while(!q.empty())
    {
        New_String tmp = q.front();
        q.pop();
        string tmp_s = tmp.s;
        if(tmp_s.find("2012") != string::npos)
        {
            cout << tmp.step << endl;
            return;
        }
        for(int i = 0; i < tmp_s.size() - 1; i++)
        {
            swap(tmp_s[i], tmp_s[i+1]);
            if(!isvisit[tmp_s])
            {
                q.push(New_String(tmp.step+1, tmp_s));
                isvisit[tmp_s] = true;
            }
            swap(tmp_s[i], tmp_s[i+1]);
        }
    }
    cout << -1 << endl;
}

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