题解 | #玛雅人的密码#

#include <bits/stdc++.h>
using namespace std;

string swap(string s, int index) {
    char temp = s[index];
    s[index] = s[index + 1];
    s[index + 1] = temp;
    return s;
}

int bfs(string s, string target, int length) { 
    int minMove = INT_MAX;
    set<string> visited;
    queue<pair<string, int>> q;
    q.emplace(s, 0);

    while (!q.empty()) {
        pair<string, int> p = q.front(); q.pop();
        if (visited.find(p.first) != visited.end()  || p.second >= minMove) continue;
        if (p.first.find(target) != string::npos) {
            minMove = min(minMove, p.second);
            continue;
        } else visited.insert(p.first);

        for (int i = 0; i < length - 1; i++)
            q.emplace(swap(p.first, i), p.second + 1);
    }
    return minMove;
}

int main() {
    string target = "2012", s;
    int length;
    cin >> length;
    cin >> s;
    cout << bfs(s, target, length) << endl;

    return 0;
}