题目描述
玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;struct Stat {char key_stat[14];int t;};char key[14];queue<Stat> Q;vector<Stat> mark;bool check(char* str, int size) {for (int i = 0; i < size-3; ++i)if (str[i] == '2' && str[i+1] == '0' && str[i+2] == '1' && str[i+3] == '2')return true;return false;
}bool travelled(char *str) {for (int i = 0; i < mark.size(); ++i)if (strcmp(mark[i].key_stat, str) == 0)return true;return false;
}int BFS() {while (!Q.empty()) {Stat front = Q.front();Q.pop();int L = strlen(front.key_stat)-1;for (int i = 0; i < L; ++i) {Stat tmp;strcpy(tmp.key_stat, front.key_stat);tmp.t = front.t + 1;char c = tmp.key_stat[i];tmp.key_stat[i] = tmp.key_stat[i+1];tmp.key_stat[i+1] = c;if (check(tmp.key_stat, strlen(tmp.key_stat)))return tmp.t;if (travelled(tmp.key_stat))continue;mark.push_back(tmp);Q.push(tmp);}}return -1;
}int main() {int N;while (scanf("%d", &N) != EOF) {if (N < 4) {printf("%d\n", -1);continue;}scanf("%s", key);if (check(key, strlen(key)))printf("%d\n", 0);else {Stat key_start;strcpy(key_start.key_stat, key);key_start.t = 0;while (!Q.empty())Q.pop();mark.clear();Q.push(key_start);printf("%d\n", BFS());}}return 0;
}