USACO Magic Squares 发表于 2016-05-01 | 分类于 USACO Training , Chapter 3 Techniques more subtle , Section 3.2 | Code123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104/* ID: wcr19961 PROG: msquare LANG: C++11*/#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;typedef long long LL;const int maxn = 10;const int maxm = 100330;const int A[maxn] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};int len[maxm], fa[maxm];char p[maxm], s[maxm];bool vis[maxm];struct node { int a[8], st; node trans(int t) { node k = *this; if (t == 0) { for (int i = 0; i < 4; ++i) { swap(k.a[i], k.a[8 - i - 1]); } } else if (t == 1) { for (int i = 3; i > 0; --i) { swap(k.a[i], k.a[i - 1]); swap(k.a[8 - i - 1], k.a[8 - i]); } } else { swap(k.a[5], k.a[6]); swap(k.a[2], k.a[5]); swap(k.a[1], k.a[2]); } k.cantor(); return k; } int cantor() { st = 0; for (int i = 0; i < 8; ++i) { int cnt = 0; for (int j = i + 1; j < 8; ++j) { if (a[i] > a[j]) { ++cnt; } } st += cnt * A[7 - i]; } return st; }} a;int main() { freopen("msquare.in", "r", stdin); freopen("msquare.out", "w", stdout); for (int i = 0; i < 8; ++i) { scanf("%d", &a.a[i]); } int aim = a.cantor(); for (int i = 0; i < 8; ++i) { a.a[i] = i + 1; } vis[a.cantor()] = true; fa[a.st] = -1, len[a.st] = 0; queue<node> q; q.push(a); while (!q.empty()) { node k = q.front(); q.pop(); if (k.st == aim) { printf("%d\n", len[aim]); int cnt = 0; while (fa[aim] != -1) { s[cnt++] = p[aim]; aim = fa[aim]; } for (int i = 0; i < cnt; ++i) { putchar(s[cnt - i - 1]); if (i % 60 == 59) { puts(""); } } if (cnt == 0 || cnt % 60 != 0) { puts(""); } return 0; } for (int i = 0; i < 3; ++i) { node x = k.trans(i); if (!vis[x.st]) { vis[x.st] = true; len[x.st] = len[k.st] + 1; fa[x.st] = k.st; p[x.st] = i + 'A'; q.push(x); } } } return 0;}