原题目：
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，表示最多容许的步数。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
评分：M超过N或者给出的操作不正确均不能得分。
算法思想及主要数据结构：
-
解题思想：采用 bfs 算法（宽度优先搜索），得到所有可能状态，然后从这些状态里面寻找对应的要达到的状态。
-
主要数据结构：queue，这⾥使⽤队列来进行bfs操作；map，⽤来保存所有能达到的状态及达到该状态的路径。
详细解题思路：
- 先找出序列经过三种移动能够达到的所有情况，通过bfs（宽度优先搜索）得到所有的序列。利用map 来储存所有能达到的状态以及达到该状态的路径。
- 注意：在使用bfs 查找所有状态的时候需要进剪枝，否则就会做很多重复操作，如操作 AA 就会得到和操作前一样的序列。如果当前得到的序列和前某个序列完全相同，那么就会重复做前那个序列的树的便利操作，这显然不是我们想要的。这个时候我们就直接抛弃这个序列及其树，也就是不进入队列。关于如果判重，所有的可能情况都是保存在 map 的，那么就可以直接判断当前得到的序列在map 是否已经存在。这使 map 的 find 法。
- 序列的保存采用的是字符串，比起整数来，字符串所占的空间更小。此时三种操作就可以通过移动字符串的字符来达到。
实现代码:
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;
void opA(const string &original, string &change);
void opB(const string &original, string &change);
void opC(const string &original, string &change);
int main() {
string change = "12348765";
map<string, string> allOp;
allOp[change].clear();
queue<string> tmp;
tmp.push(change);
while (!tmp.empty()) {
int size = tmp.size();
while (size--) {
string original = tmp.front();
opA(original, change);
if (allOp.find(change) == allOp.end()) {
allOp[change] = allOp[original]+'A';
tmp.push(change);
}
opB(original, change);
if (allOp.find(change) == allOp.end()) {
allOp[change] = allOp[original]+'B';
tmp.push(change);
}
opC(original, change);
if (allOp.find(change) == allOp.end()) {
allOp[change] = allOp[original]+'C';
tmp.push(change);
}
tmp.pop();
}
}
int maxTimes;
while (cin >> maxTimes && maxTimes != -1) {
string test;
for (int i = 0; i < 8; i++) {
int num;
cin >> num;
test += '0'+num;
}
if (allOp.find(test) != allOp.end() && allOp[test].size() <= maxTimes) {
cout << allOp[test].size() << " " << allOp[test] << endl;
} else {
cout << "-1\n";
}
}
return 0;
}
void opA(const string &original, string &change) {
change[0] = original[4];
change[1] = original[5];
change[2] = original[6];
change[3] = original[7];
change[4] = original[0];
change[5] = original[1];
change[6] = original[2];
change[7] = original[3];
}
void opB(const string &original, string &change) {
change[0] = original[3];
change[1] = original[0];
change[2] = original[1];
change[3] = original[2];
change[4] = original[7];
change[5] = original[4];
change[6] = original[5];
change[7] = original[6];
}
void opC(const string &original, string &change) {
change[0] = original[0];
change[1] = original[5];
change[2] = original[1];
change[3] = original[3];
change[4] = original[4];
change[5] = original[6];
change[6] = original[2];
change[7] = original[7];
}