# POJ1166总结

## The Clocks

### Description

```|-------|    |-------|    |-------|
|       |    |       |    |   |   |
|---O   |    |---O   |    |   O   |
|       |    |       |    |       |
|-------|    |-------|    |-------|
A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
G            H            I
(Figure 1)```

There are nine clocks in a 3*3 array (figure 1). The goal is to return all the dials to 12 o’clock with as few moves as possible. There are nine different allowed ways to turn the dials on the clocks. Each such way is called a move. Select for each move a number 1 to 9. That number will turn the dials 90′ (degrees) clockwise on those clocks which are affected according to figure 2 below.

```Move   Affected clocks

1         ABDE
2         ABC
3         BCEF
5         BDEFH
6         CFI
7         DEGH
8         GHI
9         EFHI
(Figure 2)```

### Input

Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o’clock, 1=3 o’clock, 2=6 o’clock, 3=9 o’clock.

### Output

Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o’clock. You are convinced that the answer is unique.

```3 3 0
2 2 2
2 1 2```

### Sample Output

`4 5 8 9`

### 我的代码

``````#include<stdio.h>
#include <queue>
using namespace std;
int dials[9];//记录输入的表盘
int num=10000000;//记录最短操作次数
int ans [10];//记录每一个拨法的操作次数
//moves数组在我的做法中没有用到。记录的是每一种拨法影响的表盘
int moves[10][9]={{0,0,0,0,0,0,0,0,0},
{1,1,0,1,1,0,0,0,0},
{1,1,1,0,0,0,0,0,0},
{0,1,1,0,1,1,0,0,0},
{1,0,0,1,0,0,1,0,0},
{0,1,0,1,1,1,0,1,0},
{0,0,1,0,0,1,0,0,1},
{0,0,0,1,1,0,1,1,0},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,1,1,0,1,1}};
int main ()
{
for (int i=0;i<9;i++)
{
scanf("%d",&dials[i]);
}
for (int i=0;i<4;i++)
//操作2的个数ABC
{
for(int j=0;j<4;j++)
{
for (int k=0;k<4;k++)
//操作6CFI
{
for (int m=0;m<4;m++)
//操作8的个数GHI
{
//m1,m3,m7,m9是计算得到的操作1、3、7、9的个数
int m1=(16-(dials[0]+i+j))%4;
int m3=(16-(dials[2]+i+k))%4;
int m7=(16-(dials[6]+m+j))%4;
int m9=(16-(dials[8]+k+m))%4;
//操作5的个数有五种计算方式
int m5B=(16-(dials[1]+m1+m3+i))%4;
int m5D=(16-(dials[3]+m1+m7+j))%4;
int m5E=(16-(dials[4]+m1+m3+m9+m7))%4;
int m5F=(16-(dials[5]+m9+m3+k))%4;
int m5H=(16-(dials[7]+m7+m9+m))%4;
//如果操作5的所有计算结果都一致就是可行结果
if (m5B==m5D&&m5D==m5E&&m5E==m5F&&m5F==m5H)
{
if ((m1+m3+m5B+m7+m9+i+j+k+m)<num)
//如果操作个数少就更新
{
num=(m1+m3+m5B+m7+m9+i+j+k+m);
ans[1]=m1;ans[2]=i;ans[3]=m3;ans[4]=j;ans[5]=m5B;ans[6]=k;ans[7]=m7;ans[8]=m;ans[9]=m9;
}
}
}
}
}
}
for (int i=1;i<=9;i++)
{
if (ans[i])
{
for (int j=1;j<=ans[i];j++)	printf("%d ",i);
}
}
return 0;
}``````