P2730 [USACO3.2] 魔板 Magic Squares

[USACO3.2] 魔板 Magic Squares

题目背景

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有 $8$ 个大小相同的格子的魔板：

$1234$

$8765$

题目描述

我们知道魔板的每一个方格都有一种颜色。这 $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} 来表示。这是基本状态。

这里提供三种基本操作，分别用大写字母 $\text{A}$，$\text{B}$，$\text{C}$ 来表示（可以通过这些操作改变魔板的状态）：

$\text{A}$：交换上下两行；

$\text{B}$：将最右边的一列插入最左边；

$\text{C}$：魔板中央四格作顺时针旋转。

下面是对基本状态进行操作的示范：

$\text{A}$：

$8765$

$1234$

$\text{B}$：

$4123$

$5876$

$\text{C}$：

$1724$

$8635$

对于每种可能的状态，这三种基本操作都可以使用。

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

输入格式

只有一行，包括 $8$ 个整数 $a_1,a_2\cdots a_8(1\le a_1,a_2\cdots a_8\le 8)$，用空格分开，不换行，表示目标状态。

输出格式

第一行包括一个整数，表示最短操作序列的长度。

第二行在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出 $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){//进行Aset1(s);for(int i=0;i<4;i++){swap(g[0][i],g[1][i]);}return get1();
}
string move1(string s){//进行Bset1(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){//进行Cset1(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;
}