Constraints
Time Limit: 1 secs, Memory Limit: 32 MB , Special Judge
Description
魔板由8个大小相同方块组成，分别用涂上不同颜色，用1到8的数字表示。
其初始状态是
1 2 3 4
8 7 6 5
对魔板可进行三种基本操作：
A操作（上下行互换）：
8 7 6 5
1 2 3 4
B操作（每次以行循环右移一个）：
4 1 2 3
5 8 7 6
C操作（中间四小块顺时针转一格）：
1 7 2 4
8 6 3 5
用上述三种基本操作，可将任一种状态装换成另一种状态。
Input
输入包括多个要求解的魔板，每个魔板用三行描述。
第一行步数N（可能超过10），表示最多容许的步数。
第二、第三行表示目标状态，按照魔板的形状，颜色用1到8的表示。
当N等于-1的时候，表示输入结束。
Output
对于每一个要求解的魔板，输出一行。
首先是一个整数M，表示你找到解答所需要的步数。接着若干个空格之后，从第一步开始按顺序给出M步操作（每一步是A、B或C），相邻两个操作之间没有任何空格。
注意：如果不能达到，则M输出-1即可。
Sample Input
4
5 8 7 6
4 1 2 3
3
8 7 6 5
1 2 3 4
-1
Sample Output
2 AB
1 A
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
/* 魔板状态结构体 */
struct State {
int x, y; // 魔板上下两行的状态
string op; // 从初始状态到达此状态的操作序列
State() {}
State(int a, int b, string str) : x(a), y(b), op(str) {}
} states[]; /* 判断states[index]是否为目标状态 */
bool ok(int x, int y, int index) {
if (states[index].x == x && states[index].y == y)
return true;
return false;
} /* 康托展开 ， 代码参考百度百科*/
/*（n-1）！, 1 <= n <= 8*/
int factory[] = { , , , , , , , };
int cantor(int x) {
int buf[];
/* 拆成8位， */
for (int i = ; i < ; i++) {
int p = (int)pow(, -i);
buf[i] = x / p;
x = x % p;
}
int id = ;
/* 计算康托展开 */
for (int i = ; i < ; i++) {
int count = ;
for (int j = i + ; j < ; j++)
if (buf[i] > buf[j]) count++;
id = id + count*factory[ - - i];
}
return id;
} /*A、B、C操作*/
void A(int &m, int &n, int fp) {
m = states[fp].y;
n = states[fp].x;
}
void B(int &m, int &n, int fp) {
m = (states[fp].x % ) * + (states[fp].x / );
n = (states[fp].y % ) * + (states[fp].y / );
}
void C(int &m, int &n, int fp) {
int i = (states[fp].x / )*;
int j = states[fp].x - i;
int a = j / ;
int b = (j - a * ) / ;
int i1 = (states[fp].y / ) * ;
int j1 = states[fp].y - i1;
int c = j1 / ;
int d = (j1 - c * ) / ;
m = i + c * + a * + (states[fp].x % );
n = i1 + d * + b * + (states[fp].y % );
} int main() {
int N;
while (cin >> N && N != -) {
int x = , y = , temp; // x,y记录目标魔板状态，temp：临时变量，用于从标准输入流提取数据
bool flag = false; // 标志位，true表示到达目标状态，结束搜索
bool visited[]; // 记录魔板是否已被搜索
for (int i = ; i < ; i++) visited[i] = false; // 初始化为未被搜索，即false。
for (int i = ; i < ; i++) { // 输入数据
cin >> temp;
x = x* + temp;
}
for (int i = ; i < ; i++) {
cin >> temp;
y = y* + temp;
}
if (x == && y == ) flag = true;
/* fp:头指针，即当前处理的魔板下标；rp:尾指针；l: 到达当前状态所用的步数 */
int fp = , rp = , l = ;
states[fp] = State(, ,"");
visited[cantor()] = true;
while (l < N && !flag) { //
int m = states[fp].x;
int n = states[fp].y;
/* A操作，A(int&,int&,int). 参数为引用，所以 m 和 n 的值会被改变, B,C 同理 */
A(m, n, fp);
/*
若操作后状态未被搜索， 则进队，尾指针（下标）加 1。
同时visited[index]置为true.
若为目标状态，则标志位置为true，表示找到解，同时结束循环
B,C同理
*/
if (!visited[cantor(m*+n)]) {
states[++rp] = State(m, n, states[fp].op+"A");
visited[cantor(m*+n)] = true;
if (ok(x, y, rp)) {
flag = true;
break;
}
}
B(m, n, fp);
if (!visited[cantor(m*+n)]) {
states[++rp] = State(m, n, states[fp].op+"B");
visited[cantor(m*+n)] = true;
if (ok(x, y, rp)) {
flag = true;
break;
}
}
C(m, n, fp);
if (!visited[cantor(m*+n)] ) {
states[++rp] = State(m, n, states[fp].op+"C");
visited[cantor(m*+n)] = true;
if (ok(x, y, rp)) {
flag = true;
break;
}
}
l = states[fp++].op.size(); // 计算到达当前状态需要的步数 然后头指针移到下一位
}
if (flag) cout << states[rp].op.size() << " " << states[rp].op << endl;
else cout << "-1" << endl;
}
}