题解-bfs | #密码锁#

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int n;
int bfs(string st){
    queue<string> q;
    unordered_map<string, int> d;
    q.push(st);
    d[st] = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        if(t.find("2012") != -1) return d[t];
        for(int i = 0; i < t.size() - 1; i ++){
            string r = t;
            swap(r[i], r[i + 1]);
            if(d.count(r) == 0){
                q.push(r);
                d[r] = d[t] + 1;
            }
        }
    }
    return -1;
}


int main(){
    while(cin>>n){
        string s;
        cin>>s;
        cout<<bfs(s)<<endl;
    }
    return 0;
}