清华大学上机题

清华大学上机题"/>

清华大学上机题

题目链接

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;struct node {string s;int cnt;node(string x, int y) : s(x), cnt(y) {};
};
unordered_map<string, bool> mp;
int n;bool check(string s) {if (s.size() < 4) return false;for (int i = 0; i < s.size(); i++) {string str = s.substr(i, 4);if (str == "2012") return true;}return false;
}void bfs(string s) {queue<node> q;node t(s, 0);q.push(t);mp[s] = true;while (!q.empty()) {node tmp = q.front();q.pop();if (check(tmp.s)) {cout << tmpt << endl;return;}for (int i = 0; i < tmp.s.size() - 1; i++) {string str = tmp.s;swap(str[i], str[i + 1]);if (mp.count(str) == 0) {mp[str] = true;q.push(node(str, tmpt + 1));}}}cout << -1 << endl;
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endifstring s;cin >> n >> s;bfs(s);return 0;
}