题目链接：http://acm.swust.edu.cn/problem/1126/
Time limit(ms): 1000 Memory limit(kb): 65535
上一周里，患有XX症的哈特13成功解决了填数矩阵问题。
不知道他这一周又从哪儿弄来一神奇的矩阵，于是逃课潜心研究了一周，终于发现了其中的奥秘：
该矩阵有2行、4列，即8个小方块，每个小方块上有一个数字，即：
1 2 3 4
5 6 7 8
对于这个神奇的矩阵，有3种变换方式，具体如下：
变换A：上下两行数字互换，如上图可变为：
5 6 7 8
1 2 3 4
变换B：每行同时向右循环移动一格，如上图可变为：
4 1 2 3
8 5 6 7
变换C：中间4个方块顺时针旋转90度，如上图可变为：
1 6 2 4
5 7 3 8
哈特13虽然发现了这些变换规则，但是他并不知道怎么解决如下问题：
现在给出一个初始状态和目标状态，怎么变换才能使得矩阵从初始状态变为目标状态且变换步数最少。如果有多种变换方案，输出变换序号字典序最小的那种方案。
请你帮助他。
Description
多组输入，约1000组，直到文件末尾。
每组数据包括4行，前两行为初始状态，后两行为目标状态。
Input
对于每组输入，输出满足要求的变换方案。
Output
|
1234
5678
5738
1624
|
Sample Input
| CA |
Sample Output
Sorry,由于OJ原因，换行请用\r\n
解题思路：直接从初始状态按照3种变换规则BFS,找到达到每个排列状态下的矩阵的最短路径(最少变换次数)找到对应状态下的一个序列值
(就相当于8个数全排列,直接找这是第几个排列),然后在string 数组中把每个状态的答案存贮了,到时候直接按照状态查找就是
值得注意的是每个状态下对应的记录数组的下标怎么找(这里有代码和详解：http://www.cnblogs.com/zyxStar/p/4563936.html）
注意：这里有一个坑点，那就是给出的初始序列不一定是12345678，我们需要将其对应过来(wa了n次)，具体的看代码吧~~~
#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<queue>
using namespace std;
typedef struct{
string path, mpt;
}node;
int vis[];
int cur[] = { , , , , , , , , , };
//依次为1的阶乘,2的阶乘。。。。。8各数在一个数位置确定时剩余 7！ 种排列情况,以此类推
string opera[];
/****************************************** 寻找对应状态下对应数字编号!!!!
查找 "当前数" 确定情况下剩下的 "排列"
C(n 1)*(n-i)! 当前数状确定态下的排列种数, 依次递推到最后一位叠加,
每一个状态有且只有一个数对应 *********************************************/
int get_num(string x){
int i, j, a, b, cnt = , book[];
memset(book, , sizeof(book));
for (i = ; i < ; i++){
a = x[i] - '', b = ;
for (j = ; j < a; j++){
if (!book[j])
b++;
}
cnt += b*cur[ - i];
book[a] = ;
}
return cnt + ;
}
void bfs(){
queue<node>Q;
node now, next;
now.mpt = "", now.path = "";
Q.push(now);
vis[get_num(now.mpt)] = ;
while (!Q.empty()){
now = Q.front();
Q.pop();
opera[get_num(now.mpt)] = now.path;
for (int i = ; i < ; i++){
next = now;
if (!i){
next.path += 'A';
swap(next.mpt[], next.mpt[]);
swap(next.mpt[], next.mpt[]);
swap(next.mpt[], next.mpt[]);
swap(next.mpt[], next.mpt[]);
}
else if (i == ){
next.path += 'B';
char s1 = next.mpt[];
for (int j = ; j > ; j--)
next.mpt[j] = next.mpt[j - ];
next.mpt[] = s1;
char s2 = next.mpt[];
for (int j = ; j > ; j--)
next.mpt[j] = next.mpt[j - ];
next.mpt[] = s2;
}
else{
next.path += 'C';
swap(next.mpt[], next.mpt[]);
swap(next.mpt[], next.mpt[]);
swap(next.mpt[], next.mpt[]);
}
if (!vis[get_num(next.mpt)]){
vis[get_num(next.mpt)] = ;
Q.push(next);
}
}
}
}
int main(){
bfs();
string x1, x2, y1, y2;
while (cin >> x1 >> x2 >> y1 >> y2){
x1 += x2, y1 += y2;
pair<char, char>change[];
for (int i = ; i <= ; i++){
change[i].first = x1[i - ];
change[i].second = i + '';
}
for (int i = ; i <= ; i++)
for (int j = ; j <= ; j++){
if (y1[i - ] == change[j].first){
y1[i - ] = change[j].second;
break;
}
}
cout << opera[get_num(y1)] << "\r\n";
//cout << y1;
}
return ;
}