问题解释
魔板由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
用上述三种基本操作，可将任一种状态装换成另一种状态。
额外且是最关键的要求是，从初始状态转换到最终状态的步数大于10，这太关键了，必须重视这一点。
算法思想及解题用到的主要数据结构
算法思想：队列向前搜索的算法思想，在队尾持续加入新状态，在队头移除已经处理过的旧状态，不停地进行这一步，最终我们可以搜索到满足要求的新状态。
主要数据结构：构造一颗三叉树，
只要这颗三叉树一直往下生长，如果问题有解，我们就一定能找到解（不考虑时间和空间复杂度）。具体的实现是用一个队列记录三叉树的结点。
详细解题思路
1.我们使用2个整数来代表魔板，上边为一个四位数，下面也是一个四位数。
2.我们做的第一件事情是，检查，如果2个整数一开始就是目标函数，或者说题目测试样例中给出的步数是0，那么就跳过队列搜索过程而前往最终输出处，毕竟这种情况下没必要浪费资源。
3.如果没能够跳过队列搜索，那么我们只能规规矩矩地进行三叉树的构造，先是A操作，将其结果加入队尾，再进行B操作，加入队尾，C操作，也加入队尾，而后就弹出队头，不断向前。在这个过程中，我们可能遇到两种情况，一是我们找到了答案，二是步数超出限制，这两种情况里，我们不管遇到哪一种，都要停下来。
4.一旦队列搜索停下来了，我们就可以输出了，如果队尾是答案（每往队尾插入一个新状态，我们都检测是否找到答案，是否该停），输出具体解，如果不是，输出-1即可。
5.ABC三种操作的具体实现，都是求商求模的算法，用数学的方法，修改两个4位数的各位数位置。
6.至于超时超内存，这是个值得认真考虑的问题。如果我们不进行剪枝，进行90步，将有3的90次方个状态，这是个超级计算机都无法求解的算法！如果我们进行剪枝，但剪枝的思路却是“每次加入新状态时，遍历所有已有的状态，查看是否重复”，这样将极大浪费时间，每次插入前都比较8！次，耗时不是一般的大。所以我们的结论是：必须剪枝，但剪枝需要极高效的算法。我先后考虑了康托展开hash和求模hash，发现都不是很好用，回想起c++语言的STL里set自带了红黑树构造，插入和查询还算可以，如果套用上去，将非常perfect。
为了方便，我把两个4位数进一步处理，得到一个8位数（上边的处高位，下边的处低位）
逐步求精算法描述（含过程及变量说明）
qt节点，抽象三叉树的节点，也就是队列的节点，存放状态、操作符、从根节点到目前节点的所有操作符。
qm队列，存放所有的状态。
xy set，协助剪枝，将数据插入其中失败表明该数据已经在set中。
整数xx,yy,m,n，分别是目标魔板的2个四位数和当前魔板的2个四位数。
flag，标记是否可以继续搜索。
四个过程
Add：将某操作符得到的状态封入qt节点中，并加入qm队尾，如果已经找到解，则令flag为false。
A：如果没找到解，则对qm队列队头状态求出A操作相应的状态，并检测能否插入set中，如果可以，就调用Add，将新得到的状态插入qm队列。
B：如果没找到解，则对qm队列队头状态求出B操作相应的状态，并检测能否插入set中，如果可以，就调用Add，将新得到的状态插入qm队列。
C：如果没找到解，则对qm队列队头状态求出C操作相应的状态，并检测能否插入set中，如果可以，就调用Add，将新得到的状态插入qm队列。
Type qt=record
x,y:integer;
op:char;
pre:string;
end;
Var
…,m,n,xx,yy:integer;
qm:queue of qt;
xy:set of integer;
flag:boolean;
A操作（结果存入m，n变量中）
If(!flag) then return; m:=qm.front().y; n=qm.front().x; If(xy.insert(m * 10000 + n).second) then Add(‘A’);
B操作
If(!flag) then return;
m:=(qm.front().x mod 10) *1000+(qm.front().x div 10)
n:=(qm.front().y mod 10) *1000+(qm.front().y div 10)
If(xy.insert(m * 10000 + n).second) then Add(‘B’);
C操作
If(!flag) then return; i:=(qm.front().x div 1000)*1000; j:=qm.front().x-i; a:=j div 100; b:=(j-a*100)div 10; i1:=(qm.front().y div 1000)*1000； j1:=qm.front().y-i1; c:=j1 div 100; d:=(j1-c*100)div 10; m:=i+c*100+a*10+(qm.front().x mod 10); n:=i1+d*100+b*10+(qm.front().y mod 10); If(xy.insert(m * 10000 + n).second) then Add(‘C’);
Add操作
qm.push(qt(m, n, opx, qm.front().pre + opx)); if(m == xx && n == yy) then flag = false;
程序注释清单
#include
#include
#include
#include
#include
struct qt
{
int x, y;
char op;
std::string pre;
qt(int xx, int yy, char opop, std::string prepre) {
x = xx;
y = yy;
op = opop;
pre = prepre;
}
qt() {
x = 0;
y = 0;
op = 0;
pre = "";
}
}; // 队列节点
std::queue qm;
std::set xy;
int xx, yy, m, n;
bool flag;
void Add(char opx) {
qm.push(qt(m, n, opx, qm.front().pre + opx));
if (m == xx && n == yy)
{
flag = false;
}
}
void A() {
if (!flag)
{
return;
}
m = qm.front().y;
n = qm.front().x;
// m = (qm.front().x % 100) * 100 + (qm.front().x / 100);
// n = (qm.front().y % 100) * 100 + (qm.front().y / 100);
if (xy.insert(m * 10000 + n).second)
{
Add('A');
}
}
void B() {
if (!flag)
{
return;
}
m = (qm.front().x % 10) * 1000 + (qm.front().x / 10);
n = (qm.front().y % 10) * 1000 + (qm.front().y / 10);
// m = (qm.front().x % 1000) * 10 + (qm.front().x / 1000);
// n = (qm.front().y % 1000) * 10 + (qm.front().y / 1000);
if (xy.insert(m * 10000 + n).second)
{
Add('B');
}
}
void C() {
if (!flag)
{
return;
}
int i = (qm.front().x / 1000) * 1000;
int j = qm.front().x - i;
int a = j / 100;
int b = (j - a * 100) / 10;
int i1 = (qm.front().y / 1000) * 1000;
int j1 = qm.front().y - i1;
int c = j1 / 100;
int d = (j1 - c * 100) / 10;
m = i + c * 100 + a * 10 + (qm.front().x % 10);
n = i1 + d * 100 + b * 10 + (qm.front().y % 10);
if (xy.insert(m * 10000 + n).second)
{
Add('C');
}
}
int main() {
int N;
std::cin >> N;
//N = 4;
while (N != -1)
{
while (!qm.empty())
{
qm.pop();
}
xy.clear();
int a, b, c, d;
std::cin >> a >> b >> c >> d;
xx = a * 1000 + b * 100 + c * 10 + d;
//xx = 4123;
std::cin >> a >> b >> c >> d;
yy = a * 1000 + b * 100 + c * 10 + d;
//yy = 8567;
m = 0;
n = 0;
// 如果初始状态就是解，或者步数为0
if (xx == 1234 && yy == 8765 || N == 0)
{
flag = false;
}
else
{
flag = true;
}
qm.push(qt(1234, 8765, 'x', ""));
// 把两个4位数进一步处理，得到一个8位数（上边的处高位，下边的处低位）
xy.insert(1234 * 10000 + 8765);
/**
* 如果没能够跳过队列搜索，那么我们只能规规矩矩地进行三叉树的构造
* ，先是A操作，将其结果加入队尾，再进行B操作，加入队尾，C操作，也
* 加入队尾，而后就弹出队头，不断向前。在这个过程中，我们可能遇到
* 两种情况，一是我们找到了答案，二是步数超出限制，这两种情况里，
* 我们不管遇到哪一种，都要停下来。
*/
while (flag && !qm.empty())
{
A();
B();
C();
qm.pop();
// 步数超出限制
if (qm.back().pre.size() > N)
{
flag = false;
break;
}
}
/**
* 如果队尾是答案（每往队尾插入一个新状态，我们都检测是否找到答案
* ，是否该停），输出具体解，如果不是，输出-1即可。
*/
if (qm.back().x == xx && qm.back().y == yy)
{
if (qm.back().pre.size() > 0)
{
std::cout << qm.back().pre.size() << " " << qm.back().pre << "\n";
}
else
{
std::cout << "0\n";
}
}
else
{
std::cout << "-1\n"; } std::cin >> N;
}
return 0;
}
测试数据
分析与改进
本程序里，占用时间和空间最多的，莫过于剪枝所用的set。
时间复杂度：Set的底层使用了红黑树，红黑树的特点的插入有时挺慢的（为了挪动相应的数据），但查询极快，时间复杂度是lg(N)，但是，set的插入性能有时却不好（尤其是本题这种数据间并无序的例子），为了平衡红黑树，需要调整一些数据，所以，在插入的时候，将会占用极大量的时间。但是，如果步数比较少，那使用set是很值的，因为需要做的调整比较少，费时少，但是如果步数比较多，插入的时间复杂度又将极大增加，这是个值得取舍的问题。
空间复杂度：因为set使用了红黑树，占用的存储空间会稍微大一些（为了存储节点信息）。
优化思路：正所谓，天底下没有最优算法，只有更合适的算法。没有哪种算法是最好的，也没有哪种数据结构是最好的，我们需要根据实际情况选取不同的算法和数据结构。在本题目中，如果步数仅大于10且接近于10，那么速度将极快，但是步数接近20的时候，就超时了。所以，为了处理步数接近100的例子，只能够更换另外的算法了，这里考虑康托展开。
但是实际操作中，针对测试用例34125687，康托展开的时间复杂度和我的算法的时间复杂度差不多，优点是内存占用减少50%。