拨钟问题新解
题目描述
Time limit: 10000 ms
Memory limit: 256 MB
Standard I/O
表店里有9个时钟，钟表被编号为A到I。时钟只有一个时针，在初始时，每个时钟可能指向整3点、6点、9点或12点。你被给予九种“操作”，每种操作可以将某些时钟的时间前进3小时（顺时针旋转），操作编号0到8，每种操作影响的时钟列表：
0： A B C
1： A B D E
2： A D G
3： B C E F
4： B D E F H
5： C F I
6： D E G H
7： E F H I
8： G H I
给你一个对9个时钟当前指针位置的描述，请给出一个操作数最少的操作序列，使得按照这个序列操作后，每个时钟的指针都指向12点。
输入描述
输入有若干行（不给出具体数目），每行包含以一个空格分开的9个整数，每个整数取值可能为3、6、9、12，依次标识时钟A到I的初始指针位置。不会每个指针都指向12点。
在本“完整版”，你将被一次测试全部可能的输入：4的9次方减1共262143组，而仍只有10s的时间限制。 这些输入对应的最少操作序列依旧都是唯一的（这是一个有趣的线性代数问题）。
输出描述
输出包括若干行，对应每个输入，输出最小操作序列；输入保证对应的最小操作序列是 “唯一” 的：如果将序列中的每个操作按编号升序输出的话。
在可能的情况下，行末多余的空格也会导致你 wrong answer！
逆向思维 如果可以从初始状态顺时针旋转到全12点，那么从全12点，用同样的操作序列，让其逆时针转动，就会回到初始状态，并且这个操作序列也是（唯一）最少操作的。
你需要做的可能是一个与A题相反的对称操作：将加变成减，将负数“同余”（不一定是取模）回到一定的范围。
然后，你需要做一次“全面”的初始计算：从全12点的状态出发，枚举计算到所有其他262143个时钟状态的最少（逆时针）操作序列。将这些答案存到表或数组里，然后再处理 262143 个询问。
样例输入
9 9 12 6 6 6 6 3 6
3 3 12 9 12 9 12 9 6
样例输出
2 4 7 8
1 1 1 3 4 4 4 5 5 5 6 6 6 7 7 8
通常情况下我们使用九重循环的方法暴力求解.但是这里我们有如此海量的数据,直接九重循环定然超时.
为此,我们需要削减循环次数.
从最后一步考虑.我们此时还剩下几个钟,只需要一次操作即可复原为12点.由于拨钟的顺序不影响结果(比如你先拨AB,再拨AC与先AC后AB是一样的),所以最后剩余的钟我们是可以任意定义的.
观察我们的所有操作.可以发现,只有操作1同时对ABC进行操作,故我们将最后的三个钟设定为ABC.于是我们得到如下思路:
通过op1-op8八个操作,使得最后只剩下ABC未复原,且ABC状态相同.因为只有状态相同的情况才可以通过op0一步到位.
现在我们只需要考虑6个钟了.与ABC相同,我们可以将这六个钟再度划分为DEF与GHI.由于只有op8是对GHI同时操作的.我们需要:
通过op1-op7七个操作,使得最后只剩下GHI未复原,且状态相同.
由于op8与op0互不干扰,所以上述条件应当同时成立.总而言之:
通过op1-op7七个操作,使得DEF全部复位,而ABC与GHI分别处于某个相同状态.
于是我们的循环变为7重,总共减少了次运算.
代码如下:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
int main(void) {
int Alarm[9] = { 0 };
while (scanf("%d%d%d%d%d%d%d%d%d", &Alarm[0], &Alarm[1],
&Alarm[2], &Alarm[3], &Alarm[4], &Alarm[5], &Alarm[6], &Alarm[7], &Alarm[8])==9) {
int i;
for (i = 0; i < 9; i++) {
Alarm[i] = (Alarm[i] / 3) % 4;
}
int OpNum[10];
int Answer[10];
Answer[9] = 50;
for (OpNum[1] = 0; OpNum[1] < 4; OpNum[1]++) {
for (OpNum[2] = 0; OpNum[2] < 4; OpNum[2]++) {
for (OpNum[3] = 0; OpNum[3] < 4; OpNum[3]++) {
for (OpNum[4] = 0; OpNum[4] < 4; OpNum[4]++) {
for (OpNum[5] = 0; OpNum[5] < 4; OpNum[5]++) {
for (OpNum[6] = 0; OpNum[6] < 4; OpNum[6]++) {
for (OpNum[7] = 0; OpNum[7] < 4; OpNum[7]++) {
if ((OpNum[1] + OpNum[2] + OpNum[4] + OpNum[6] + Alarm[3]) % 4 == 0 &&
(OpNum[1] + OpNum[3] + OpNum[4] + OpNum[6] + OpNum[7] + Alarm[4]) % 4 == 0 &&
(OpNum[3] + OpNum[4] + OpNum[5] + OpNum[7] + Alarm[5]) % 4 == 0) {
int A0= ( OpNum[1] + OpNum[2] + Alarm[0]) % 4;
int A1 = (OpNum[1] + OpNum[3] + OpNum[4] + Alarm[1]) % 4;
int A2 = ( OpNum[3] + OpNum[5] + Alarm[2]) % 4;
if (A0==A1 && A1==A2) {
int A6 = (OpNum[2] + OpNum[6] + Alarm[6]) % 4;
int A7 = (OpNum[4] + OpNum[6] + OpNum[7] + Alarm[7]) % 4;
int A8 = (OpNum[5] + OpNum[7]+ Alarm[8]) % 4;
if (A6==A7&&A7==A8 ) {
OpNum[0] = (4 - A0) % 4;
OpNum[8] = (4 - A8) % 4;
OpNum[9] = OpNum[0] + OpNum[1] + OpNum[2] + OpNum[3] + OpNum[4] + OpNum[5] + OpNum[6] + OpNum[7] + OpNum[8];
if (OpNum[9] < Answer[9]) {
memcpy(Answer, OpNum, 10 * sizeof(int));
}
}
}
}
}
}
}
}
}
}
}
for (i = 0; i < 8; i++) {
for (int j = 0; j < Answer[i]; j++) {
printf("%d ", i);
}
}
if (Answer[8] != 0) {
for (int j = 0; j < Answer[8] - 1; j++) {
printf("8 ");
}
printf("8\n");
}
else {
putchar('\n');
}
}
return 0;
}
在codia平台上测试,6853ms通过.比起九重循环快了将近一倍.
这里快了近一倍还有一个因素,在于if判断语句上面.我们并不需要计算出所有情况再判断,边算边判断会节省大量时间.
