|
#include <fstream>
using namespace std;
const int with[10][5]={{},{1,2,4,5},{1,2,3},{2,3,5,6},{1,4,7},{2,4,5,6,8},{3,6,9},{4,5,7,8},{7,8,9},{5,6,8,9}};
char t[270000][10],way[270000]={1},use[270000][10];
int pre[270000];
string ans;
void bfs();
bool check(int);
void work(int,int,int);
int main() {
ifstream fin ("clocks.in");
ofstream fout ("clocks.out");
for (int i=1,tem;i<=9;i++) {
fin >> tem;
t[0][i]=tem%12;
}
bfs();
fout << ans << endl;
fin.close();
fout.close();
return 0;
}
void bfs() {
int tail=0,head=-1;
while (tail>head) {
head++;
for (int i=way[head];i<=9;i++) if (use[head][i]<3){
work(i,head,++tail);
way[tail]=i;
pre[tail]=head;
for (int j=1;j<=9;j++) use[tail][j]=use[head][j];
use[tail][i]++;
if (check(tail)) {
ans=char(way[tail]+'0');
for (int j=pre[tail];j!=0;j=pre[j]) {
ans=' '+ans;
ans=char(way[j]+'0')+ans;
}
return;
}
}
}
}
bool check(int k) {
for (int i=1;i<=9;i++) if (t[k][i]!=0) return false;
return true;
}
void work(int k,int from,int cur) {
for (int i=1;i<=9;i++) t[cur][i]=t[from][i];
for (int i=0;i<=4 && with[k][i]!=0;i++) t[cur][with[k][i]]=(t[from][with[k
  /**//*
 ID:greenwo1
PROG: clocks
LANG:C++
 */
 #include<cstdio>
#include<cstdlib>
#include<string>
//#include<cmath>
//#include<algorithm>
//#include<queue>
#include<iostream>
using namespace std;
int slu[100],way[100],cur[9],used[9];//hulue 3*9ci maximum times
int mini=1000000;
//int move[9]={110110000,111000000,011011000,100100100,
//010111010,001001001,000110110,000000111,000011011};
int move[9]= {110110000,111000000,11011000,100100100,
10111010,1001001,110110,111,11011};
bool judge(int* arr)
{
int i;
for(i=0;i<9;i++)
if(*(arr+i)!=12)return 0;
return 1;
}
int convert(int k)
{
if(k/10)
return k%10+2*convert(k/10);
else return k%10;
}
void dfs(int* path,int m,int t)
{
int i,j,k;
if(m>mini||m>27)return;
  /**//*if(m==27)
 printf("dfs:%d\n",m);*/
if(judge(cur))
{
if(m<mini)
{
mini=m;
//memcpy(way,slu,mini*sizeof(int));
for(i=0;i<mini;++i)
way[i]=slu[i];
}
return ;
}
for(i=t;i<9;i++)
{
if(used[i]>=3)continue;
if(used[i]<3)
{
*(path)=i;
k=move[i];
used[i]++;
//printf("dfs:%d %d %d\n",m,i,used[i]);
for(j=0;j<9;j++)
{
if(k&1<<(8-j))cur[j]=(cur[j]+3);
if(cur[j]>12)cur[j]-=12;
}
dfs(path+1,m+1,i);
for(j=0;j<9;j++)
{
if(k&1<<(8-j))cur[j]=(cur[j]-3);
if(cur[j]<=0)cur[j]+=12;
}
used[i]--;
}
}
}
int main()
{
int i,j,k,n;
FILE* fin,*fout;
fin=fopen("clocks.in","r");
fout=fopen("clocks.out","w");
for(i=0;i<9;i++)
{
move[i]=convert(move[i]);
}
for(i=0;i<9;++i)
fscanf(fin,"%d",&cur[i]);
for(i=0;i<9;i++)
{
slu[0]=i;
k=move[i];
used[i]++;
//printf("dfs:%d %d %d\n",m,i,used[i]);
for(j=0;j<9;j++)
{
if(k&1<<(8-j))cur[j]=(cur[j]+3);
if(cur[j]>12)cur[j]-=12;
}
dfs(slu+1,1,i);
for(j=0;j<9;j++)
{
if(k&1<<(8-j))cur[j]=(cur[j]-3);
if(cur[j]<=0)cur[j]+=12;
}
used[i]--;
}
//printf("%d\n",mini);
fprintf(fout,"%d",way[0]+1);
for(k=1;k<mini;k++)fprintf(fout," %d",way[k]+1);
fprintf(fout,"\n");
return 0;
}][i]]+3)%12;
} |