時(shí)限：1000ms?內(nèi)存限制：10000K ?總時(shí)限：3000ms

描述：

現(xiàn)有一兩行三列的表格如下：
A B C
D E F
把1、2、3、4、5、6六個數(shù)字分別填入A、B、C、D、E、F格子中，每個格子一個數(shù)字且各不相同。每種不同的填法稱為一種布局。如下：

1 3 5
2 4 6
布局1
2 5 6
4 3 1
布局2

定義α變換如下：把A格中的數(shù)字放入B格，把B格中的數(shù)字放入E格，把E格中的數(shù)字放入D格，把D格中的數(shù)字放入A格。
定義β變換如下：把B格中的數(shù)字放入C格，把C格中的數(shù)字放入F格，把F格中的數(shù)字放入E格，把E格中的數(shù)字放入B格。
問：對于給定的布局，可否通過有限次的α變換和β變換變成下面的目標(biāo)布局：
1 2 3
4 5 6
目標(biāo)布局

輸入：

本題有多個測例，每行一個，以EOF為輸入結(jié)束標(biāo)志。每個測例的輸入是1到6這六個數(shù)字的一個排列，空格隔開，表示初始布局ABCDEF格中依次填入的數(shù)字。

輸出：

每個輸出占一行。可以轉(zhuǎn)換的，打印Yes；不可以轉(zhuǎn)換的，打印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 //一個節(jié)點(diǎn)便是一種狀態(tài) {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};//狀態(tài)標(biāo)記 int num[6];//六個格子里填的數(shù)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時(shí)不會有breakbreak;if(i==6) printf("Yes");//初始填的就是目標(biāo)布局temp=1else{ 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進(jìn)行變換，新的狀態(tà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;//新狀態(tài)加入隊(duì)列 addtoopen(v); }}}}return 0;//無法從初始狀態(tài)到目標(biāo)狀態(tài) } struct openode takeoutopen() {struct openode u=open[head++];head=head%openlen;return u; } int canmove(int i,struct openode u,struct openode *v)//判斷狀態(tài)u之后能否更據(jù)i進(jìn)入下一狀態(tài) {*v=u;//u是當(dāng)前狀態(tài)，v是下一狀態(tài)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;elsereturn 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++)//狀態(tài)表置0for(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++)//隊(duì)列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格中依次填入的數(shù)字open[0].a=num[0];//初始布局入隊(duì)列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（實(shí)際走的步長為0） }

轉(zhuǎn)載于:https://www.cnblogs.com/IThaitian/archive/2012/07/16/2594436.html

總結(jié)

以上是生活随笔為你收集整理的六数码问题（广搜_队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。