相对1150题来说，这道题的N可能超过10，所以需要进行排重，即相同状态的魔板不要重复压倒队列里，这里我用map储存操作过的状态，也可以用康托编码来储存状态，这样时间缩短为0.03秒。关于康托展开可以参考，其可用数学归纳法证明：http://www.cnblogs.com/1-2-3/archive/2011/04/25/generate-permutation-part2.html
#include <bits/stdc++.h>
using namespace std;
map<int, int>visit;
int op_a(int n) {//操作A（上下行互换）
int low = n % ;
int high = n / ;
return low * + high;
} int op_b(int n) {//操作B（每次以行循环右移一个）
int low = n % ;
int high = n / ;
int h = high % ;
high = h * + high / ;
int l = low % ;
low = l * + low / ;
return high * + low;
} int op_c(int n) {//操作C（中间四小块顺时针转一格）
int a[];
for (int i = ; i < ; i++) {
a[-i] = n % ;
n = n / ;
}
int ans = a[] * +
a[] * +
a[] * +
a[] * +
a[] * +
a[] * +
a[] * +
a[];
return ans;
}
struct Node {
int num;//num储存状态，用8位的十进制数来储存状态
vector<char> path;//path储存操作
};
Node bfs(int step, int n) {
queue<Node> q;
Node front;
front.num = ;//初始的魔板
visit[front.num] = ;
q.push(front);
if(front.num == n)return front; while (!q.empty()) {
front = q.front();
q.pop();
if (front.path.size() > step) {
return front;//如果操作的次数大于step数，返回
}
//依次进行三种操作
Node tmp1 = front; tmp1.num = op_a(front.num);
tmp1.path.push_back('A');
if (tmp1.num == n) {
return tmp1;
}
else if(visit.find(tmp1.num) == visit.end()){
visit[tmp1.num] = ;
q.push(tmp1);
} Node tmp2 = front;
tmp2.num = op_b(front.num);
tmp2.path.push_back('B');
if (tmp2.num == n) {
return tmp2;
}
else if(visit.find(tmp2.num) == visit.end()){
visit[tmp2.num] = ;
q.push(tmp2);
} Node tmp3 = front;
tmp3.num = op_c(front.num);
tmp3.path.push_back('C');
if (tmp3.num == n) {
return tmp3;
}
else if(visit.find(tmp3.num) == visit.end()){
visit[tmp3.num] = ;
q.push(tmp3);
} }
}
int main(){
int step;
while (cin >> step && step != -) {
int ans = ;
int a;
for (int i = ; i < ; i++) {//将魔板转换成数字
cin >> a;
ans = * ans + a;
} visit.clear();
Node node = bfs(step, ans);
if (node.path.size() > step) cout << "-1" << endl;//如失败则输出-1，否则输出path
else {
cout << node.path.size() << " ";
for (int i = ; i < node.path.size(); i++) {
cout << node.path[i];
}
cout << endl;
} }
return ;
}