文章目录
IOI'94 - Day 2
Consider nine clocks arranged in a 3x3 array thusly:
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause
the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.
| Move | Affected clocks |
| 1 | ABDE |
| 2 | ABC |
| 3 | BCEF |
| 4 | ADG |
| 5 | BDEFH |
| 6 | CFI |
| 7 | DEGH |
| 8 | GHI |
| 9 | EFHI |
Example
Each number represents a time accoring to following table:
9 9 12 9 12 12 9 12 12 12 12 12 12 12 12 6 6 6 5 -> 9 9 9 8-> 9 9 9 4 -> 12 9 9 9-> 12 12 12 6 3 6 6 6 6 9 9 9 12 9 9 12 12 12
[But this might or might not be the `correct' answer; see below.]
PROGRAM NAME: clocks
INPUT FORMAT
| Lines 1-3: | Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above. |
SAMPLE INPUT (file clocks.in)
9 9 12 6 6 6 6 3 6
OUTPUT FORMAT
A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated
(e.g., 5 2 4 6 < 9 3 1 1).
SAMPLE OUTPUT (file clocks.out)
4 5 8 9
/*
ID: conicoc1
LANG: C
TASK: clocks
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
void Move1(int *Clocks)
{
Clocks[A]+=3;
Clocks[B]+=3;
Clocks[D]+=3;
Clocks[E]+=3;
}
void Move2(int *Clocks)
{
Clocks[A]+=3;
Clocks[B]+=3;
Clocks[C]+=3;
}
void Move3(int *Clocks)
{
Clocks[B]+=3;
Clocks[C]+=3;
Clocks[E]+=3;
Clocks[F]+=3;
}
void Move4(int *Clocks)
{
Clocks[A]+=3;
Clocks[D]+=3;
Clocks[G]+=3;
}
void Move5(int *Clocks)
{
Clocks[B]+=3;
Clocks[D]+=3;
Clocks[E]+=3;
Clocks[F]+=3;
Clocks[H]+=3;
}
void Move6(int *Clocks)
{
Clocks[C]+=3;
Clocks[F]+=3;
Clocks[I]+=3;
}
void Move7(int *Clocks)
{
Clocks[D]+=3;
Clocks[E]+=3;
Clocks[G]+=3;
Clocks[H]+=3;
}
void Move8(int *Clocks)
{
Clocks[G]+=3;
Clocks[H]+=3;
Clocks[I]+=3;
}
void Move9(int *Clocks)
{
Clocks[E]+=3;
Clocks[F]+=3;
Clocks[H]+=3;
Clocks[I]+=3;
}
int IsFinished(int *Clocks)
{
int i;
for(i=0;i<9;i++)
if(Clocks[i]%12!=0)
return 0;
return 1;
}
void swap(int *a,int *b)
{
int i;
for(i=0;i<9;i++)
a[i]=b[i];
}
int main()
{
FILE *fin,*fout;
fin=fopen("clocks.in","r");
fout=fopen("clocks.out","w");
int Clocks[9],temp[9];
int M[9],P[9]={0},Sum=28; //记录每种移动方式的次数
int i,j,k,t;
for(i=0;i<9;i++)
{
fscanf(fin,"%d",&Clocks[i]);
}
swap(temp,Clocks);
for(M[0]=0;M[0]<=3;M[0]++)
{
for(M[1]=0;M[1]<=3;M[1]++)
{
for(M[2]=0;M[2]<=3;M[2]++)
{
for(M[3]=0;M[3]<=3;M[3]++)
{
for(M[4]=0;M[4]<=3;M[4]++)
{
for(M[5]=0;M[5]<=3;M[5]++)
{
for(M[6]=0;M[6]<=3;M[6]++)
{
for(M[7]=0;M[7]<=3;M[7]++)
{
for(M[8]=0;M[8]<=3;M[8]++)
{
for(i=0;i<9;i++)
{
for(j=0;j<M[i];j++)
switch(i)
{
case 0:Move1(Clocks);break;
case 1:Move2(Clocks);break;
case 2:Move3(Clocks);break;
case 3:Move4(Clocks);break;
case 4:Move5(Clocks);break;
case 5:Move6(Clocks);break;
case 6:Move7(Clocks);break;
case 7:Move8(Clocks);break;
case 8:Move9(Clocks);break;
}
}
if(IsFinished(Clocks))
{
if(Sum>M[0]+M[1]+M[2]+M[3]+M[4]+M[5]+M[6]+M[7]+M[8])
{
for(k=0;k<9;k++)
{
P[k]=M[k];
}
Sum=M[0]+M[1]+M[2]+M[3]+M[4]+M[5]+M[6]+M[7]+M[8];
}
// getchar();
}
swap(Clocks,temp);
}
}
}
}
}
}
}
}
}
k=0;
t=0;
for(i=0;i<9;i++)
{
for(j=0;j<P[i];j++)
{
k++;
}
}
for(i=0;i<9;i++)
{
for(j=0;j<P[i];j++)
{
fprintf(fout,"%d",i+1);
t++;
if(t!=k)
fprintf(fout," ");
}
}
fprintf(fout,"\n");
return 0;
}
虐啊。。太虐了。。做到1.4就开始虐了。。。
让我回想一下我开始的各种想法。。
一开始以为选择移动的9种方式是有优先权的。。。不停的再想优先权，想了半天不对。
后来模拟了一下已知的过程，对于给定的9个钟，方法的顺序可以不一样，所以就有了那个坑爹的解九元一次方程组，还专门复习了一下矩阵的高斯消元，
折腾了半天发现等式右边是4n-1或2或3，是不定的，思考无果。放弃
最后实在没办法了，就只好用暴力了
对于每种方法最多只能执行3次，因为4次就等于没有动，所以开辟了一个数组存放每种方法的执行次数。
本打算一旦找到符合的，就弹出循环，后来样例3检测的时候出错了，发现需要比较所有可能的情况，选数组和最低的情况。
另外最后所要求的输出方法，每个数字之间有空格，最后和开头没有空格，对于整体输出想了半天没有什么好的方法，结果码了一大串。。。
去NOCOW上面研究一下BFS和DFS的方法。对于深搜和广搜的理解还是不够深刻啊啊。
/*
ID: conicoc1
LANG: C
TASK: barn1
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int Stack[3000000];
int Queue[3000000];
int Flag[3000000];
int road[3000000][2];
int top=0,front=0,rear=0;
int clock[9];
int temp[9];
void act(int p)
{
int i,j,k;
if(p==1)
{
clock[0]=(clock[0]+1)%4;
clock[1]=(clock[1]+1)%4;
clock[3]=(clock[3]+1)%4;
clock[4]=(clock[4]+1)%4;
}
if(p==2)
{
clock[0]=(clock[0]+1)%4;
clock[1]=(clock[1]+1)%4;
clock[2]=(clock[2]+1)%4;
}
if(p==3)
{
clock[2]=(clock[2]+1)%4;
clock[1]=(clock[1]+1)%4;
clock[5]=(clock[5]+1)%4;
clock[4]=(clock[4]+1)%4;
}
if(p==4)
{
clock[0]=(clock[0]+1)%4;
clock[3]=(clock[3]+1)%4;
clock[6]=(clock[6]+1)%4;
}
if(p==5)
{
clock[5]=(clock[5]+1)%4;
clock[1]=(clock[1]+1)%4;
clock[3]=(clock[3]+1)%4;
clock[4]=(clock[4]+1)%4;
clock[7]=(clock[7]+1)%4;
}
if(p==6)
{
clock[2]=(clock[2]+1)%4;
clock[5]=(clock[5]+1)%4;
clock[8]=(clock[8]+1)%4;
}
if(p==7)
{
clock[6]=(clock[6]+1)%4;
clock[7]=(clock[7]+1)%4;
clock[3]=(clock[3]+1)%4;
clock[4]=(clock[4]+1)%4;
}
if(p==8)
{
clock[6]=(clock[6]+1)%4;
clock[7]=(clock[7]+1)%4;
clock[8]=(clock[8]+1)%4;
}
if(p==9)
{
clock[8]=(clock[8]+1)%4;
clock[7]=(clock[7]+1)%4;
clock[5]=(clock[5]+1)%4;
clock[4]=(clock[4]+1)%4;
}
}
int invert()
{
int i,sum=0;
int n=1;
for(i=0;i<9;i++)
{
sum+=clock[i]*n;
n*=4;
}
return sum;
}
void revert(int sum)
{
int i;
for(i=0;i<9;i++)
{
clock[i]=sum%4;
sum/=4;
}
}
void InStack(int s)
{
if(s==Queue[0])
{
return;
}
// printf("%d %d\n",s,road[s][0]);
InStack(road[s][0]);
Stack[top++]=road[s][1]; //最下面是根
}
int main()
{
FILE *fin,*fout,*ftxt;
fin=fopen("clocks.in","r");
fout=fopen("clocks.out","w");
memset(Flag,-1,sizeof(Flag));
memset(road,-1,sizeof(road));
int i,j,k;
for(i=0;i<9;i++)
{
fscanf(fin,"%d",&clock[i]);
clock[i]=(clock[i]/3)%4;
}
int s,t; //保存转换的状态
s=invert();
Queue[rear++]=s; //将该状态进队
printf("rear:%d,s:%d,Queue[0]:%d",rear,s,Queue[0]);
Flag[s]=1;
while(front!=rear)
{
s=Queue[front++];
revert(s);
for(j=0;j<9;j++)
temp[j]=clock[j];
for(i=1;i<=9;i++)
{
act(i);
t=invert();
// printf("%d\n",t);
if(t==0)
getchar();
if(Flag[t]==-1)
{
Flag[t]=1;
Queue[rear++]=t;
road[t][0]=s;
road[t][1]=i;
}
for(j=0;j<9;j++)
clock[j]=temp[j];
}
if(Flag[0]==1)
break;
}
// for(j=0;j<9;j++)
// printf("%d",clock[j]);
//接下来将路径递归进栈
InStack(0);
for(i=0;i<top;i++)
printf("%d ",Stack[i]);
}
这个方法对我这个菜鸟来说感觉很有应用价值啊