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
4 ADG
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.
Sample Input
3 3 0 2 2 2 2 1 2
Sample Output
4 5 8 9
我的代码
通过分析可知每一个拨法一共有4种操作次数（0次、1次、2次、3次），做n次（n>=4）的效果和做n-4次是一样的。
然后每一种拨法都会引起若干表盘指针顺时针变化90°，由此可得能操作每一个表盘的拨法。
表盘A：1、2、4
表盘B：1、2、3、5
表盘C：2、3、6
表盘D：1、4、5、7
表盘E：1、3、5、7、9
表盘F：3、5、6、9
表盘G：4、7、8
表盘H：5、7、8、9
表盘I：6、8、9
现在只要对拨法2、4、6、8的操作次数进行暴力，就可以算出剩下来5种拨法的次数。例如根据表盘A，知道了拨法2、4的次数就能得到拨法1的次数，等等。
#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++)
//操作4的个数ADG
{
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;
}反思
很想用bfs来做这道题，但是爆栈了，也不知道有没有解决的方法。
网上还有用高斯消元法做的，但是我不会，以后再研究吧。