考虑将如此安排在一个 3 x3 行列中的九个时钟：
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
目标要找一个最小的移动顺序次将所有的指针指向12点。下面原表格列出了9种不同的旋转指针的方法，每一种方法都叫一次移
动。选择1到9号移动方法，将会使在表格中对应的时钟的指针顺时针旋转90度。
移动方法 受影响的时钟
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI
Example：
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
[但这可能不是正确的方法，请看下面]
INPUT FORMAT:
(file clocks.in)
第1-3行: 三个空格分开的数字，每个数字表示一个时钟的初始时间，3,6,9,12。数字的含意和上面第一个例子一样。
OUTPUT FORMAT:
(file clocks.out)
单独的一行包括一个用空格分开的将所有指针指向12:00的最短移动顺序的列表。
如果有多种方案，输出那种使其连接起来数字最小的方案。(举例来说5 2 4 6 < 9 3 1 1)。
input：
9 9 12
6 6 6
6 3 6
output：
4 5 8 9
【参考程序】：
/*
ID: XIONGNA1
PROG: clocks
LANG: C++
*/
#include<iostream>
using namespace std;
int a[10],ans[401],temp[401];
int la,lt;
bool tf()
{
if (lt>la) return false;
if (lt<la) return true;
for (int i=1;i<=la;i++)
if (ans[i]<temp[i]) return false;
return true;
}
void make(int &x)
{
x+=3;
if (x>12) x-=12;
}
void change(int *no3,int k)
{
/*
A:make(no3[1]);B:make(no3[2]);C:make(no3[3]);
D:make(no3[4]);E:make(no3[5]);F:make(no3[6]);
G:make(no3[7]);H:make(no3[8]);I:make(no3[9]);
*/
switch (k)
{
case 1:
make(no3[1]);make(no3[2]);
make(no3[4]);make(no3[5]);
break;
case 2:
make(no3[1]);make(no3[2]);
make(no3[3]);break;
case 3:
make(no3[2]);make(no3[3]);
make(no3[5]);make(no3[6]);
break;
case 4:
make(no3[1]);make(no3[4]);
make(no3[7]);break;
case 5:
make(no3[2]);make(no3[4]);
make(no3[5]);make(no3[6]);
make(no3[8]);break;
case 6:
make(no3[3]);make(no3[6]);
make(no3[9]);break;
case 7:
make(no3[4]);make(no3[5]);
make(no3[7]);make(no3[8]);
break;
case 8:
make(no3[7]);make(no3[8]);
make(no3[9]);break;
case 9:
make(no3[5]);make(no3[6]);
make(no3[8]);make(no3[9]);
break;
}
}
bool check(int *no4)
{
for (int i=1;i<=9;i++)
if (no4[i]!=12) return false;
return true;
}
void dfs(int *no1,int p)
{
if (p>9) return ;
dfs(no1,p+1);
int no2[10];
for (int i=1;i<=9;i++) no2[i]=no1[i];
for (int i=1;i<=3;i++)
{
lt++;temp[lt]=p;
if (!tf()) return ;
change(no2,p);
if (check(no2))
{
la=lt;
for (int i=1;i<=la;i++) ans[i]=temp[i];
return ;
}
else dfs(no2,p+1);
}
lt-=3;
}
int main()
{
freopen("clocks.in","r",stdin);
freopen("clocks.out","w",stdout);
for (int i=1;i<=9;i++) scanf("%d",&a[i]);
for (int i=1;i<=400;i++) ans[i]=9;
la=400;lt=0;
dfs(a,1);
for (int i=1;i<=la-1;i++) printf("%d ",ans[i]);
printf("%d\n",ans[la]);
return 0;
}