NC22946. 魔板
描述
在成功地发明了魔方之后，拉比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板：
| 1 | 2 | 3 | 4 |
| 8 | 7 | 6 | 5 |
我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。
下面是对基本状态进行操作的示范：
| A: |
| B: |
| C: |
|
对于每种可能的状态，这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。
输入描述
只有一行，包括8个整数，用空格分开（这些整数在范围 1——8 之间），表示目标状态。
输出描述
Line 1: 包括一个整数，表示最短操作序列的长度。
Line 2: 在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。
示例1
输入:
2 6 8 4 5 7 3 1
输出:
7 BCABCCB
C++(clang++11) 解法, 执行用时: 92ms, 内存消耗: 6004K, 提交时间: 2021-02-24 13:34:33
#include<bits/stdc++.h>
using namespace std;
string a;
map<string,string>m;
queue<string>q;
void A(string x)
{
string xx=x;
for(int i=0;i<4;i++)
{
char x1=x[i];
x[i]=x[7-i];
x[7-i]=x1;
}
if(m.count(x)==0)
{
q.push(x);
m[x]=m[xx]+'A';
}
return;
}
void B(string x)
{
string xx=x;
x[0]=xx[3],x[1]=xx[0],x[2]=xx[1],x[3]=xx[2],x[4]=xx[5],x[5]=xx[6],x[6]=xx[7],x[7]=xx[4];
if(m.count(x)==0)
{
q.push(x);
m[x]=m[xx]+'B';
}
return;
}
void C(string x)
{
string xx=x;
x[1]=xx[6],x[2]=xx[1],x[5]=xx[2],x[6]=xx[5];
if(m.count(x)==0)
{
q.push(x);
m[x]=m[xx]+'C';
}
return;
}
void bfs()
{
q.push("12345678");
m["12345678"]="";
while(q.empty()==false)
{
A(q.front());
B(q.front());
C(q.front());
if(m.count(a)!=0)
{
cout<<m[a].size()<<endl<<m[a];
return;
}
q.pop();
}
return;
}
int main()
{
for(int i=0;i<8;i++)
{
char a1;
cin>>a1;
a+=a1;
getchar();
}
bfs();
return 0;
}