AcWing 3385. 玛雅人的密码
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
int t, n, m, k, l, r, op, x, y;
string str;
struct nd {
string s;
int step;
};
unordered_set<string> st;
void solve() {
cin >> n >> str;
int siz = str.size();
queue<nd>q;
q.push({str, 0});
st.insert(str);
while (!q.empty()) {
auto &[s, step] = q.front();
if (s.find("2012") != string::npos) {
cout << step;
return;
}
for (int i = 1; i < siz; i++) {
swap(s[i - 1], s[i]);
if (st.find(s) == st.end()) {
st.insert(s);
q.push({s, step + 1});
}
swap(s[i - 1], s[i]);
}
q.pop();
}
cout << -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}