题解 | #密码锁# 恶心

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

int n;
string s;

struct New_string{
    string s;
    int step;
    New_string(string s, int x): s(s), step(x){}
};

unordered_map<string, bool> visit;
void bfs(string s)
{
    queue<New_string> q;
    q.push(New_string(s, 0));
    visit[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(!visit[tmp_s])
            {
                q.push(New_string(tmp_s, tmp.step+1));
                visit[tmp_s] = true;
            }
            swap(tmp_s[i], tmp_s[i+1]);
        }
    }
    cout << -1 << endl;
}

int main() {
    while(cin >> n >> s)
    {
        visit.clear();
        bfs(s);
    }
}
// 64 位输出请用 printf("%lld")