[USACO3.2] 魔板 Magic Squares
题目背景
在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有 8 8 8 个大小相同的格子的魔板：
1 2 3 4 1\quad2\quad3\quad4 1234
8 7 6 5 8\quad7\quad6\quad5 8765
题目描述
我们知道魔板的每一个方格都有一种颜色。这 8 8 8 种颜色用前 8 8 8 个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } \{1,2,3,4,5,6,7,8\} {1,2,3,4,5,6,7,8} 来表示。这是基本状态。
这里提供三种基本操作，分别用大写字母 A \text A A， B \text B B， C \text C C 来表示（可以通过这些操作改变魔板的状态）：
A \text A A：交换上下两行；
B \text B B：将最右边的一列插入最左边；
C \text C C：魔板中央四格作顺时针旋转。
下面是对基本状态进行操作的示范：
A \text A A：
8 7 6 5 8\quad7\quad6\quad5 8765
1 2 3 4 1\quad2\quad3\quad4 1234
B \text B B：
4 1 2 3 4\quad1\quad2\quad3 4123
5 8 7 6 5\quad8\quad7\quad6 5876
C \text C C：
1 7 2 4 1\quad7\quad2\quad4 1724
8 6 3 5 8\quad6\quad3\quad5 8635
对于每种可能的状态，这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。
输入格式
只有一行，包括 8 8 8 个整数 a 1 , a 2 ⋯ a 8 ( 1 ≤ a 1 , a 2 ⋯ a 8 ≤ 8 ) a_1,a_2\cdots a_8(1\leq a_1,a_2\cdots a_8\leq8) a1,a2⋯a8(1≤a1,a2⋯a8≤8)，用空格分开，不换行，表示目标状态。
输出格式
第一行包括一个整数，表示最短操作序列的长度。
第二行在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出 60 60 60 个字符。
样例 #1
样例输入 #1
2 6 8 4 5 7 3 1
样例输出 #1
7
BCABCCB
提示
题目翻译来自 NOCOW。
USACO Training Section 3.2
code:
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
int g[2][4];
unordered_map<string ,int >dist;//存到当前状态需要几步
unordered_map<string,pair<char ,string > >pre;//存从哪一个状态转移过来的，而且要存A还是B还是C操作(char是存ABC,pair中的string是存从哪一个状态转移过来的)pre[s]={‘A或B或C’,t};
queue<string>q;
void set1(string s){//把字符串转化为2*4的矩阵,并且要顺时针存储
for(int i=0;i<4;i++){
g[0][i]=s[i];
}
for(int i=3,j=4;i>=0;i--,j++){
g[1][i]=s[j];
}
}
string get1(){//把2*4的矩阵转化为字符串
string res;
for(int i=0;i<4;i++){
res+=g[0][i];//字符串加减就是字符串的拼接
}
for(int i=3;i>=0;i--){
res+=g[1][i];
}
return res;
}
string move0(string s){//进行A
set1(s);
for(int i=0;i<4;i++){
swap(g[0][i],g[1][i]);
}
return get1();
}
string move1(string s){//进行B
set1(s);
char v0=g[0][3],v1=g[1][3];//把最后一列数存起来，然后把其他位置都往后移动一位
for(int i=3;i>0;i--){
for(int j=0;j<2;j++){
g[j][i]=g[j][i-1];
}
}
g[0][0]=v0;
g[1][0]=v1;
return get1();
}
string move2(string s){//进行C
set1(s);//先把左上角的数存起来，然后直接转一圈，类似于冒泡
char tmp=g[0][1];
g[0][1]=g[1][1];
g[1][1]=g[1][2];
g[1][2]=g[0][2];
g[0][2]=tmp;
return get1();
}
int bfs(string start,string end1){
q.push(start);
dist[start]=0;
while(q.size()){
auto t=q.front();
q.pop();
if(t==end1){
return dist[end1];
}
string m[3];
m[0]=move0(t);
m[1]=move1(t);
m[2]=move2(t);
for(int i=0;i<3;i++){
string s=m[i];
if(!dist.count(s)){//如果s状态没有被访问过则可以去访问
dist[s]=dist[t]+1;
pre[s]={char(i+'A'),t};//i+'A'可以把0，1，2···，转化为A，B，C，s表示下一个状态
if(s==end1){
return dist[end1];
}
q.push(s);
}
}
}
return -1;
}
int main(){
int x;
string start,end1;
for(int i=1;i<=8;i++){
cin>>x;
end1+=char(x+'0');//数字变字符，+'0'
}
for(int i=1;i<=8;i++){
start+=char(i+'0');
}
int res=bfs(start,end1);
cout<<res<<endl;
string res2;
while(end1!=start){//从目标状态往起始状态开始存储，所以最终答案需要翻转
res2+=pre[end1].first;//字符串的拼接
end1=pre[end1].second;
}
reverse(res2.begin(),res2.end());//翻转最终答案
if(res2.size()){
cout<<res2<<endl;
}
return 0;
}