Consider nine clocks arranged in a 3×3 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
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.]

## INPUTFORMAT

 Line1: 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.

## OUTPUTFORMAT

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).

## SOLUTION

### 广度优先搜索

bfs另一个麻烦的问题是内存空间。我把储存节点的struct中int改成了short int，然后又改成了char，算了算，一个节点占49字节，满足要求，这才过的。说实话，我是第一次这么一个字节一个字节地锱铢必较。源码如下：

/*
ID:tom.tun1
PROG:clocks
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("clocks.in");
ofstream fout("clocks.out");
struct
{
char Time[9];//九个钟表的状态：0,3,6,9
char depth;//当前节点的深度
char num[28];//记录到达该节点的各个操作编号
char operate_times[9 + 1];//operate_times[i]的值为已经进行i操作的次数
char operation;//记录直接得到本节点的操作
}Clocks[270000];
const char operate[9 + 1][6] =
{
/*每个操作影响的钟表号，每个操作的序列以-1结尾*/
0, 0, 0, 0, 0, 0, 0, 1, 3, 4, -1, 0, 0, 1, 2, -1, 0, 0, 1, 2, 4, 5, -1, 0,
0, 3, 6, -1, 0, 0, 1, 3, 4, 5, 7, -1, 2, 5, 8, -1, 0, 0, 3, 4, 6, 7, -1, 0,
6, 7, 8, -1, 0, 0, 4, 5, 7, 8, -1, 0
};

int
main()
{
/*输入及初始化*/
for (int i = 0,c; i < 9; i++)
{
fin >> c;
if (c == 12)
c = 0;
Clocks[0].Time[i] = c + '0';
}
Clocks[0].depth = 0;
Clocks[0].operation = 1;
memset(Clocks[0].operate_times, 0, sizeof(Clocks[0].operate_times));

/*BFS*/
int head = 0, tail = 1;/*首尾指针*/
bool flag = true;
while (flag && head < tail)
{
i <= 9;
i++)/*生成的i对应操作的编号*/
{
/*如果某操作执行超过3次则取消本次循环*/
if (Clocks[head].operate_times[i] + 1 > 3)
continue;

/*产生节点*/
for (int j = 0; operate[i][j] != -1; j++)
{
int n = operate[i][j];
Clocks[tail].Time[n] = '0';
else
}
/*operate_times[]部份*/
sizeof(Clocks[0].operate_times));
Clocks[tail].operate_times[i]++;
Clocks[tail].operation = i;/*operation部份*/
/*节点产生完毕*/

/*判断是否达到目标节点*/
flag = false;
for (int j = 0; j < 9; j++)
if (Clocks[tail].Time[j] != '0')
{
flag = true;
break;
}
if (!flag)
break;
tail++;
}
}

/*输出答案*/
for (int i = 0; i < strlen(Clocks[tail].num); i++)
{
if (i == strlen(Clocks[tail].num) - 1)
fout << Clocks[tail].num[i] << endl;
else
fout << Clocks[tail].num[i] << ' ';
}
//system("pause");
return 0;
}


### 深度优先搜索

/*
ID:tom.tun1
PROG:clocks
LANG:C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("clocks.in");
ofstream fout("clocks.out");
struct Clocks
{
char Time[9];//九个钟表的状态：0,3,6,9
int depth;//当前节点的深度
char num[28];//记录到达该节点的各个操作编号
int operate_times[9 + 1];//operate_times[i]的值为已经进行i操作的次数
}FirstClock;
const char operate[9 + 1][6] =
{
/*每个操作影响的钟表号，每个操作的序列以-1结尾*/
0, 0, 0, 0, 0, 0, 0, 1, 3, 4, -1, 0, 0, 1, 2, -1, 0, 0, 1, 2, 4, 5, -1, 0,
0, 3, 6, -1, 0, 0, 1, 3, 4, 5, 7, -1, 2, 5, 8, -1, 0, 0, 3, 4, 6, 7, -1, 0,
6, 7, 8, -1, 0, 0, 4, 5, 7, 8, -1, 0
};
char min_num[28], min_depth = 30;
void
search(struct Clocks Clock, int i)//DFS递归函数，Clock为当前节点，i操作编?
{
/*节点产生*/
struct Clocks NextClock;
/*depth部分*/
NextClock.depth = Clock.depth + 1;
if (NextClock.depth > min_depth)
return;
/*num部分*/
strcpy(NextClock.num, Clock.num);
NextClock.num[NextClock.depth - 1] = i + '0';
/*Time[9]部分*/
strcpy(NextClock.Time, Clock.Time);
for (int j = 0; operate[i][j] != -1; j++)
{
int n = operate[i][j];
if (Clock.Time[n] == '9')
NextClock.Time[n] = '0';
else
NextClock.Time[n] = Clock.Time[n] + 3;
}
/*operate_times部分*/
memcpy(NextClock.operate_times, Clock.operate_times,
sizeof(Clock.operate_times));
if (++NextClock.operate_times[i] > 3)
return;

/*检查是否为目标节点*/
if (strcmp(NextClock.Time, "000000000") == 0)
{
/*更新min_depth和min_num的值*/
if (NextClock.depth < min_depth)
{
strcpy(min_num, NextClock.num);
min_depth = NextClock.depth;
return;
}
}

/*递归*/
for (int j = i; j <= 9; j++)
search(NextClock, j);
}
int
main()
{
/*输入及初始化*/
for (int i = 0,c; i < 9; i++)
{
fin >> c;
if (c == 12)
c = 0;
FirstClock.Time[i] = c + '0';
}
FirstClock.depth = 0;
memset(FirstClock.operate_times, 0, sizeof(FirstClock.operate_times));

/*DFS*/
for (int i = 1; i <= 9; i++)
search(FirstClock, i);

/*输出答案*/
for (int i = 0; i < min_depth; i++)
{
if (i == min_depth - 1)
fout << min_num[i] << endl;
else
fout << min_num[i] << ' ';
}
return 0;
}


### 特殊方法

** Lucian Boca提交了一种常数时间的解法 **

a[i][0],a[i][1],….,a[i][8]是“仅仅”将第i个钟表（0<=i<=8，共有9个钟表：0=A, 1=B, … 8=I）顺时针转动90度所必须的操作1、2、3…9的执行次数。这样你就得到了一个矩阵：

int a[9][9]= {
{3,3,3,3,3,2,3,2,0},
{2,3,2,3,2,3,1,0,1},
{3,3,3,2,3,3,0,2,3},
{2,3,1,3,2,0,2,3,1},
{2,3,2,3,1,3,2,3,2},
{1,3,2,0,2,3,1,3,2},
{3,2,0,3,3,2,3,3,3},
{1,0,1,3,2,3,2,3,2},
{0,2,3,2,3,3,3,3,3}
};


#include <stdio.h>

int a[9][9]= { {3,3,3,3,3,2,3,2,0},
{2,3,2,3,2,3,1,0,1},
{3,3,3,2,3,3,0,2,3},
{2,3,1,3,2,0,2,3,1},
{2,3,2,3,1,3,2,3,2},
{1,3,2,0,2,3,1,3,2},
{3,2,0,3,3,2,3,3,3},
{1,0,1,3,2,3,2,3,2},
{0,2,3,2,3,3,3,3,3} };
int v[9];

int main() {
int i,j,k;
freopen("clocks.in","r",stdin);
for (i=0; i<9; i++) {
scanf("%d",&k);
for(j=0; j<9; j++)
v[j]=(v[j]+(4-k/3)*a[i][j])%4;
}
fclose(stdin);

k=0;
freopen("clocks.out","w",stdout);
for (i=0; i<9; i++)
for (j=0; j<v[i]; j++)
if (!k) { printf("%d",i+1); k=1; }
else    printf(" %d",i+1);
printf("\n");
fclose(stdout);
return 0;
}


program clocks;
const
INV : array[3..12] of byte =(1, 0, 0, 2, 0, 0, 3, 0, 0, 0);

var inp, out: text;
a, b, c, d, e, f, g, h, i: integer;
ax, bx, cx, dx, ex, fx, gx, hx, ix,l: integer;
t,an: array[1..9] of integer;
begin
assign (inp, 'clocks.in'); reset (inp);
a:=inv[ax]; b:=inv[bx]; c:=inv[cx]; d:=inv[dx];
e:=inv[ex]; f:=inv[fx]; g:=inv[gx]; h:=inv[hx];
i:=inv[ix];
t[1] := (8+a+2*b+c+2*d+2*e-f+g-h) mod 4;
t[2] := (a+b+c+d+e+f+2*g+    2*i) mod 4;
t[3] := (8+  a+2*b+  c  -d+2*e+2*f      -h+  i) mod 4;
t[4] := (    a+  b+2*c+  d+  e+      g+  h+2*i) mod 4;
t[5] := (4+  a+2*b+  c+2*d  -e+2*f+  g+2*h+  i) mod 4;
t[6] := (  2*a+  b+  c+      e+  f+2*g+  h+  i) mod 4;
t[7] := (8+  a  -b+    2*d+2*e  -f+  g+2*h+  i) mod 4;
t[8] := (  2*a+    2*c+  d+  e+  f+  g+  h+  i) mod 4;
t[9] := (8      -b+  c  -d+2*e+2*f+  g+2*h+  i) mod 4;
assign(out, 'clocks.out'); rewrite(out);
for a := 1 to 9 do
for b := 1 to t[a] do Begin
inc(l);
an[l]:=a;
end;
for a:=1 to l-1 do
write(out,an[a],' ');
write(out,an[l]);
writeln(out); close(out)
end.
`