时限：1000ms 内存限制：10000K 总时限：3000ms
描述：
现有一两行三列的表格如下：
A B C
D E F
把1、2、3、4、5、6六个数字分别填入A、B、C、D、E、F格子中，每个格子一个数字且各不相同。每种不同的填法称为一种布局。如下：
1 3 5
2 4 6
布局1
2 5 6
4 3 1
布局2
定义α变换如下：把A格中的数字放入B格，把B格中的数字放入E格，把E格中的数字放入D格，把D格中的数字放入A格。
定义β变换如下：把B格中的数字放入C格，把C格中的数字放入F格，把F格中的数字放入E格，把E格中的数字放入B格。
问：对于给定的布局，可否通过有限次的α变换和β变换变成下面的目标布局：
1 2 3
4 5 6
目标布局
输入：
本题有多个测例，每行一个，以EOF为输入结束标志。每个测例的输入是1到6这六个数字的一个排列，空格隔开，表示初始布局ABCDEF格中依次填入的数字。
输出：
每个输出占一行。可以转换的，打印Yes；不可以转换的，打印No。
输入样例：
1 3 5 2 4 6
2 5 6 4 3 1
输出样例：
No
Yes
#include<stdio.h> #include<stdlib.h> #define N 10000//注意open表的长度 struct openode //一个节点便是一种状态 { int a; int b; int c; int d; int e; int f; }; struct openode open[N]={0}; int openlen=N,head=0,tail=0; int s[6][6][6][6][6][6]={0};//状态标记 int num[6];//六个格子里填的数 void init(); int search(); void addtoopen(struct openode u); struct openode takeoutopen(); int isaim(struct openode v); int used(struct openode v); int canmove(int i,struct openode u,struct openode *v); //////////////////////////////////////////////////////////////////// int main() { int temp; while(scanf("%d",&num[0])!=EOF) { init(); for(int i=0;i<6;i++) if(num[i]!=i+1)//六个格子依次填1-2-3-4-5-6时不会有break break; if(i==6) printf("Yes");//初始填的就是目标布局temp=1 else { temp=search(); if(temp==0) printf("No\n"); else printf("Yes\n"); } } return 0; } /////////////////////////////////////////////////////////////////////////////// int search() { struct openode u,v; while(head!=tail) { u=takeoutopen(); int num=s[u.a][u.b][u.c][u.d][u.e][u.f]; for(int i=0;i<2;i++)//两种变换方式 { if(canmove(i,u,&v))//更具i进行变换，新的状态保存在v中 { if(isaim(v)) return(num);//注意返回的是num(初始位置处步长置为1) else if(!used(v)) { s[v.a][v.b][v.c][v.d][v.e][v.f]=num+1;//新状态加入队列 addtoopen(v); } } } } return 0;//无法从初始状态到目标状态 } struct openode takeoutopen() { struct openode u=open[head++]; head=head%openlen; return u; } int canmove(int i,struct openode u,struct openode *v)//判断状态u之后能否更据i进入下一状态 { *v=u;//u是当前状态，v是下一状态 if(i==0) { int temp=v->a; v->a=v->d; v->d=v->e; v->e=v->b; v->b=temp; if(s[v->a][v->b][v->c][v->d][v->e][v->f]==0) return 1; return 0; } if(i==1) { int temp=v->b; v->b=v->e; v->e=v->f; v->f=v->c; v->c=temp; if(s[v->a][v->b][v->c][v->d][v->e][v->f]==0) return 1; return 0; } } int isaim(struct openode v) { if(v.a==1 &&v.b==2 &&v.c==3 &&v.d==4 &&v.e==5 &&v.f==6) return 1; else return 0; } int used(struct openode v) { if(s[v.a][v.b][v.c][v.d][v.e][v.f]==1) return 1; return 0; } void addtoopen(struct openode u) { open[tail++]=u; tail=tail%openlen; } ///////////////////////////////////////////////////////////////////////////////// void init() { int i1,i2,i3,i4,i5,i6; for(i1=0;i1<6;i1++)//状态表置0 for(i2=0;i2<6;i2++) for(i3=0;i3<6;i3++) for(i4=0;i4<6;i4++) for(i5=0;i5<6;i5++) for(i6=0;i6<6;i6++) s[i1][i2][i3][i4][i5][i6]=0; for(int i=0;i<10000;i++)//队列open表置空 { open[i].a=0; open[i].b=0; open[i].c=0; open[i].d=0; open[i].e=0; open[i].f=0; } for(i=1;i<6;i++) scanf("%d",&num[i]);//初始布局ABCDEF格中依次填入的数字 open[0].a=num[0];//初始布局入队列 open[0].b=num[1]; open[0].c=num[2]; open[0].d=num[3]; open[0].e=num[4]; open[0].f=num[5]; tail=1; s[num[0]][num[1]][num[2]][num[3]][num[4]][num[5]]=1;//初始位置处步长置为1（实际走的步长为0） }