BFS+预处理。
一组解的话Usaco有题。。。要是T组解的话就预处理一下。
#include <cstdio> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define rep(i, l, r) for(int i=l; i<=r; i++) #define down(i, l, r) for(int i=l; i>=r; i--) #define maxn 40320 #define MAX 1<<30 using namespace std; struct node{int n[9], c;} p; int a, o, c, n[maxn], v[maxn], ans[maxn]; bool b[maxn]; char s[9], t[9]; int Cal(node p) { bool b[9]; rep(i, 1, 8) b[i] = false; int a = 0, c = 1; rep(i, 1, 8) { rep(j, p.n[i]+1, 8) if (b[j]) a += c; c *= i; b[p.n[i]] = true; } return a; } int main() { queue <node> q; rep(i, 1, 8) p.n[i] = i; b[Cal(p)] = true; p.c = 0; q.push(p); while (!q.empty()) { p = q.front(); q.pop(); o = Cal(p); a = p.n[1], p.n[1] = p.n[8], p.n[8] = a; a = p.n[2], p.n[2] = p.n[7], p.n[7] = a; a = p.n[3], p.n[3] = p.n[6], p.n[6] = a; a = p.n[4], p.n[4] = p.n[5], p.n[5] = a; p.c++; if (!b[Cal(p)]) { int x = Cal(p); q.push(p); b[x] = true; v[x] = 1; n[x] = o; } p.c--; a = p.n[1], p.n[1] = p.n[8], p.n[8] = a; a = p.n[2], p.n[2] = p.n[7], p.n[7] = a; a = p.n[3], p.n[3] = p.n[6], p.n[6] = a; a = p.n[4], p.n[4] = p.n[5], p.n[5] = a; a = p.n[1], p.n[1] = p.n[4], p.n[4] = p.n[3], p.n[3] = p.n[2], p.n[2] = a; a = p.n[5], p.n[5] = p.n[6], p.n[6] = p.n[7], p.n[7] = p.n[8], p.n[8] = a; p.c++; if (!b[Cal(p)]) { int x = Cal(p); q.push(p); b[x] = true; v[x] = 2; n[x] = o; } p.c--; a = p.n[1], p.n[1] = p.n[2], p.n[2] = p.n[3], p.n[3] = p.n[4], p.n[4] = a; a = p.n[5], p.n[5] = p.n[8], p.n[8] = p.n[7], p.n[7] = p.n[6], p.n[6] = a; a = p.n[2], p.n[2] = p.n[7], p.n[7] = p.n[6], p.n[6] = p.n[3], p.n[3] = a; p.c++; if (!b[Cal(p)]) { int x = Cal(p); q.push(p); b[x] = true; v[x] = 3; n[x] = o; } p.c--; a = p.n[2], p.n[2] = p.n[3], p.n[3] = p.n[6], p.n[6] = p.n[7], p.n[7] = a; } while (scanf("%s%s", s, t) != EOF) { rep(i, 1, 8) rep(j, 1, 8) if (t[i-1] == s[j-1]) p.n[i] = j; o = Cal(p); c = 0; while (o) { ans[++c] = v[o]; o = n[o]; } down(i, c, 1) printf("%c", ans[i]-1+'A'); printf(" "); } return 0; }