【搜索】北京2008的挂钟——BSOI 1678

挂钟——BSOI 1678"/>

【搜索】北京2008的挂钟——BSOI 1678

【题目描述】

在2008北京奥运会雄伟的主会场的墙上，挂着如上图所示的3*3的九个挂钟（一开始指针即时针指向的位置请根据输入数据调整）。然而此次奥运会给与了大家一个机会，去用最少的移动操作改变上面的挂钟的时间全部为12点正（我们只考虑时针）。然而每一次操作并不是任意的，我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行，每一个挂钟顺时针转动90度。列表如下：

操作 指定的操作挂钟
1　　　　 ABDE
2　　　　 ABC
3　　　　 BCEF
4　　　　 ADG
5　　　　 BDEFH
6　　　　 CFI
7　　　　 DEGH
8　　　　 GHI
9　　　　 EFHI

【输入格式】

你的程序按照标准的3*3格式读入，一共9个0-3的数。0代表12点，1代表3点，2代表6点，3代表9点。

【输出格式】

        你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向12点的移动操作序列，中间以空格隔开，最后有空格，加回车。这一条最短操作需要是所有最短操作中最小的，也就是说选择最小的第一个操作数，如果第一个操作数相等，那么选择最小的第二个操作数……以此类推。值得肯定的是，这一条操作序列是唯一的。

【输入样例】

3 3 0 2 2 2 2 1 2

【输出样例】

4 5 8 9

【题目解析】

拿到这道题，我们最先想到的就是直接暴力模拟，而暴力的方法就是搜索，这道题的数据不大，显然深搜或者广搜都是可以的，只不过限制条件有点多罢了。我们可以先拿一个数组存题目中要求的变化方式，时钟一共4种形式，所以我们搜索的最终时间复杂度也不会太高，然后再hash判重开一个九维的数组存每种情况变化的次数就行了。（只是有点难写罢了qvq）

【代码】

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read(){//习惯打快读  int s=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}return s*f;
}
struct cl{//用来存当前的9个钟的状态，步数和之前的变化方式 int p[10];int step[40],num;
};
int n=3,m=3,a[10],f[4][4][4][4][4][4][4][4][4];//f存每种情况变化的最少次数 
//                   change数组存9种变化方式 
//                     A B C D E F G H I
int change[10][10]={{0,0,0,0,0,0,0,0,0,0},//0{0,1,1,0,1,1,0,0,0,0},//1{0,1,1,1,0,0,0,0,0,0},//2{0,0,1,1,0,1,1,0,0,0},//3{0,1,0,0,1,0,0,1,0,0},//4{0,0,1,0,1,1,1,0,1,0},//5{0,0,0,1,0,0,1,0,0,1},//6{0,0,0,0,1,1,0,1,1,0},//7{0,0,0,0,0,0,0,1,1,1},//8{0,0,0,0,0,1,1,0,1,1}};//9
queue<cl>q;//用于广搜的队列 
bool pd(cl x){//判断是否所有时钟都指向12点 int i,j,k;for(i=1;i<=9;i++){if(x.p[i]!=0)return false;}return true;
}
int main(){int i,j,k;for(i=1;i<=9;i++){a[i]=read();}cl dzh;memcpy(dzh.p,a,sizeof(a));//将 a 数组复制至 dzh.p 数组 q.push(dzh);//存入时钟初始状态 memset(f,0x3f,sizeof(f));f[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=0;//初始状态步数为0 while(q.size()){cl now=q.front();if(now.num>=30)continue;//因为每种变化方式进行4次就会变回原样，所以最多搜大约30次 if(pd(now)){//判断是否所有时钟都指向12时 for(i=1;i<=now.num;i++)printf("%d ",now.step[i]);return 0;}int st=f[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.p[7]][now.p[8]][now.p[9]];q.pop();for(i=1;i<=9;i++){cl to=now;for(j=1;j<=9;j++){if(change[i][j]==1){to.p[j]=(to.p[j]+1)%4;//变化一次即为将 0变成1，1变成2，2变成3，3变成0， 
                }}int st_to=f[to.p[1]][to.p[2]][to.p[3]][to.p[4]][to.p[5]][to.p[6]][to.p[7]][to.p[8]][to.p[9]];if(st_to>st+1){//更新状态 f[to.p[1]][to.p[2]][to.p[3]][to.p[4]][to.p[5]][to.p[6]][to.p[7]][to.p[8]][to.p[9]]=st+1;to.step[++to.num]=i;q.push(to);}}}return 0;
}

转载于:.html