BFS
题目描述
Rubik 先生在发明了风靡全球的魔方之后,又发明了它的二维版本——魔板。
这是一张有8个大小相同的格子的魔板:
1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。
这8种颜色用前8个正整数来表示。
可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。
对于上图的魔板状态,我们用序列 (1,2,3,4,5,6,7,8)来表示,这是基本状态。
这里提供三种基本操作,分别用大写字母 A,B,C 来表示(可以通过这些操作改变魔板的状态):
A:交换上下两行;
B:将最右边的一列插入到最左边;
C:魔板中央对的4个数作顺时针旋转。
下面是对基本状态进行操作的示范:
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
对于每种可能的状态,这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。
注意:数据保证一定有解。
输入格式
输入仅一行,包括8个整数,用空格分开,表示目标状态.
输出格式
输出文件的第一行包括一个整数,表示最短操作序列的长度。
如果操作序列的长度大于0,则在第二行输出字典序最小的操作序列。
数据范围
输入数据中的所有数字均为1到8之间的整数。
输入样例:
2 6 8 4 5 7 3 1
输出样例:
7
BCABCCB
感觉没啥好说的,就是枚举每一种可能,存一下转移来的pre,最后递归输出即可.
参考代码
#include<bits/stdc++.h>
using namespace std;
const int N=9*9*9*9*9*9*9;
int head,tail;
int ans[8];
bool vis[9][9][9][9][9][9][9];
int now[N][8],pre[N],r[8],u[N],bz[N];
inline int write(int x) {
if(pre[x]!=-1)write(pre[x]);
if(bz[x]==1)cout<<"A";
if(bz[x]==2)cout<<"B";
if(bz[x]==3)cout<<"C";
return 0;
}
int main() {
for(int i=0; i<8; i++) cin>>ans[i];
head=1;
tail=1;
u[1]=0;
for(int k=0; k<8; k++) now[head][k]=k+1;
vis[now[tail][0]][now[tail][1]][now[tail][2]][now[tail][3]][now[tail][4]][now[tail][5]][now[tail][6]]=true;
pre[1]=-1;
while(tail<=head) {
if(now[tail][0]==ans[0]&&now[tail][1]==ans[1]&&now[tail][2]==ans[2]&&now[tail][3]==ans[3]&&now[tail][4]==ans[4]&&now[tail][5]==ans[5]&&now[tail][6]==ans[6]&&now[tail][7]==ans[7]) {
cout<<u[tail]<<endl;
write(tail);
return 0;
}
r[0]=now[tail][7];
r[1]=now[tail][6];
r[2]=now[tail][5];
r[3]=now[tail][4];
r[7]=now[tail][0];
r[6]=now[tail][1];
r[5]=now[tail][2];
r[4]=now[tail][3];
if(!vis[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]]) {
head++;
for(int k=0; k<=8; k++) now[head][k]=r[k];
pre[head]=tail;
bz[head]=1;
vis[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]]=true;
u[head]=u[tail]+1;
}
r[0]=now[tail][3];
r[1]=now[tail][0];
r[2]=now[tail][1];
r[3]=now[tail][2];
r[7]=now[tail][4];
r[6]=now[tail][7];
r[5]=now[tail][6];
r[4]=now[tail][5];
if(!vis[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]]) {
head++;
for(int k=0; k<=8; k++)now[head][k]=r[k];
pre[head]=tail;
bz[head]=2;
vis[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]]=true;
u[head]=u[tail]+1;
}
r[0]=now[tail][0];
r[1]=now[tail][6];
r[2]=now[tail][1];
r[3]=now[tail][3];
r[7]=now[tail][7];
r[6]=now[tail][5];
r[5]=now[tail][2];
r[4]=now[tail][4];
if(!vis[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]]) {
head++;
for(int k=0; k<=8; k++)now[head][k]=r[k];
pre[head]=tail;
bz[head]=3;
vis[r[0]][r[1]][r[2]][r[3]][r[4]][r[5]][r[6]]=true;
u[head]=u[tail]+1;
}
tail++;
}
return 0;
}
tql!!!
tql!!!!
tql!!!
tql