A39799. 拨钟问题
填空题
中等
知识点
题目描述
拨钟问题
题目描述
有9个钟，排成一个3*3的矩阵。
现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如下表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。
移动方法 受影响的时钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
输入
9个整数，表示各时钟指针的起始位置，相邻两个整数之间用单个空格隔开。其中，0=12点，1=3点，2=6点，3=9点。
输出
单独的一行包括一个用空格分开的将所有指针指向 12 点的最短移动顺序的列表。
如果有多种方案，输出那种使其连接起来的数字最小的方案。(举例来说 5 2 4 6 < 9 3 1 1)。
样例输入
3 3 0
2 2 2
2 1 2
样例输出
4 5 8 9
参考答案
#include<stdio.h>
#define cir(i) for(int i=0;i<4;i++)
int main()
{
int a[10],b[10];
int min;
int sum;
while(~scanf("%d",&a[0]))
{
min=2e9;
for(int i=1;i<9;i++) scanf("%d",&a[i]);
int i5,i6,i7,i8,i9;
cir(i1)cir(i2)cir(i3)cir(i4)
{
if((i1+i2+i4+a[0])%4==0)//确定了A
{
i5=(4-(i1+i2+i3+a[1])%4)%4;//确定了B
i6=(4-(i2+i3+a[2])%4)%4;//确定了C
i7=(4-(i1+i4+i5+a[3])%4)%4;//确定了D
i8=(4-(i4+i7+a[6])%4)%4;//确定了G
i9=(4-(i1+i3+i5+i7+a[4])%4)%4;//确定了E
//i1-i9确定完毕，下面分别验证F,H,I.
if((i3+i5+i6+i9+a[5])%4==0&&(i5+i7+i8+i9+a[7])%4==0&&(i6+i8+i9+a[8])%4==0)
{
sum=i1+i2+i3+i4+i5+i6+i7+i8+i9;
if(sum<min)
{
min=sum;
b[0]=i1;
b[1]=i2;
b[2]=i3;
b[3]=i4;
b[4]=i5;
b[5]=i6;
b[6]=i7;
b[7]=i8;
b[8]=i9;
}
}
}
}
for(int i=0;i<9;i++)
{
while(b[i]--)
printf("%d ",i+1);
}
printf("\n");
}
return 0;
}
上一题
下一题