题解 | #玛雅人的密码#

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int MAXN = 10001;

struct data1 {
    string str;
    int depth;
    data1(string str, int depth): str(str), depth(depth) {};
};

void solve(string str) {
    map<string, int> m;
    queue<data1> myQueue;
    myQueue.push(data1(str, 0));
    while (!myQueue.empty()) {
        data1 current = myQueue.front();
        myQueue.pop();
        if (current.str.find("2012") != string::npos) {
            cout << current.depth << endl;
            return;
        }
        for (int i = 1; i < str.size() - 1; i++) {
            for (int j = 0; j < 2; j++) {
                string str = current.str;

                if (j == 0) {
                    swap(str[i], str[i - 1]);

                } else {
                    swap(str[i], str[i + 1]);
                }
                if (m[str] == 1) continue;
                else m[str] = 1;
                myQueue.push(data1(str, current.depth + 1));
            }

        }
    }
}
int main() {
    int n;
    string str;
    while (cin >> n) {
        cin >> str;
        solve(str);
    }
}