由于1.4.1太WS了,我就先看了下后面三个,一开始看这个,感觉是一个简单的BFS,而且和数据结构书上的迷宫算法应该差不多,就写了个,可是我写好了后,发现第三组数据过不掉……,要不就是数组太小了,越界,要不就是数组不够大,反正我找不到一个合适的,而且本人刚写搜索算法,以前对搜索有一点恐惧(莫名的恐惧),不过现在好了,看来还是要写几个啊,呵呵。而且这题有放在搜索这一章,于是我该数组改了20多次,一直过不掉,后来搜了分解题报告,人家说9重循环,我一看就蒙了,9重?不过这倒是个不错的想法,而且时间要求不多,就4^9次,因为每一个转4次和没转是一样的。
下面附个官方的吧,(那个9重循环的对于没其他想法的人可以一试,毕竟那样是自己写出来的。)

Notice that the order in which we apply moves is irrelevant, and that applying a move four times is the same as applying it not at all.

Thus there are only 49 = 262144 move sequences that need to be tried, so we might as well just try them all.

We don't generate them shortest first, but looking at sequences of the same length, we generate the lesser ones before the greater ones, so we only need to keep track of the shortest working sequence we've found.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#define INF 60000	/* bigger than longest possible path */
char *movestr[] = { "abde", "abc", "bcef", "adg", "bdefh", "cfi", "degh",
"ghi", "efhi" };
int movedist[9][9];
int clock[9];
int bestmove[9];
int nbestmove;
/* translate move strings into array "movedist" of which clocks change on each move */
void  mkmove(void)
{
int i;
char *p;
for(i=0; i<9; i++)
for(p=movestr[i]; *p; p++)
movedist[i][*p-'a'] = 3;
}
/* apply some number of each move from k to 9 */
/* move contains the number of times each move is applied */
void  solve(int *move, int k)
{
int i, j, n, rep;
if(k == 9) {
for(j=0; j<9; j++)
if(clock[j]%12 != 0)
return;
/* we have a successful sequence of moves */
n = 0;
for(j=0; j<9; j++)
n += move[j];
if(nbestmove == 0 || n < nbestmove) {
nbestmove = n;
for(j=0; j<9; j++)
bestmove[j] = move[j];
}
return;
}
/*
* the for loop counts down so we
* generate smaller numbers first by
* trying more of small numbered
* moves before we try less of them.
*/
for(rep=3; rep>=0; rep--) {
/* apply move k rep times */
for(i=0; i<rep; i++)
for(j=0; j<9; j++)
clock[j] += movedist[k][j];
move[k] = rep;
solve(move, k+1);
/* undo move */
for(i=0; i<rep; i++)
for(j=0; j<9; j++)
clock[j] -= movedist[k][j];
}
}
void  main(void)
{
FILE *fin, *fout;
int i, j, move[9];
char *sep;
fin = fopen("clocks.in", "r");
fout = fopen("clocks.out", "w");
assert(fin != NULL && fout != NULL);
mkmove();
for(i=0; i<9; i++)
fscanf(fin, "%d", &clock[i]);
solve(move, 0);
sep = "";
for(i=0; i<9; i++) {
for(j=0; j<bestmove[i]; j++) {
fprintf(fout, "%s%d", sep, i+1);
sep = " ";
}
}
fprintf(fout, "\n");
exit(0);
}