题目链接：http://acm.ocrosoft.com/problem.php?cid=1615&pid=16

题目描述：

在2008北京奥运会雄伟的主会场的墙上，挂着如上图所示的3*3的九个挂钟（一开始指针即时针指向的位置请根据输入数据调整）。然而此次奥运会给与了大家一个机会，去用最少的移动操作改变上面的挂钟的时间全部为12点正（我们只考虑时针）。然而每一次操作并不是任意的，我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行，每一个挂钟顺时针转动90度。列表如下：

 

操作 指定的操作挂钟

1 ABDE

2 ABC

3 BCEF

4 ADG

5 BDEFH

6 CFI

7 DEGH

8 GHI

9 EFHI

输入

你的程序按照标准的3*3格式读入，一共9个0-3的数。0代表12点，1代表3点，2代表6点，3代表9点。

输出

你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向12点的移动操作序列，中间以空格隔开，最后有空格，加回车。这一条最短操作需要是所有最短操作中最小的，也就是说选择最小的第一个操作数，如果第一个操作数相等，那么选择最小的第二个操作数……以此类推。值得肯定的是，这一条操作序列是唯一的。

样例输入：

3 3 0
2 2 2
2 1 2

样例输出：

4 6 8 9

 思路：用一个DFS直接暴力搜索即可，用3个数组，分别记录输入的数据，操作时拷贝输入数据的数组以及每种操作各使用的次数的数组。

代码：

#include<iostream>
using namespace std;
int dir[9][9] = {		{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} };//每一行表示1,2,3,4,5,6,7,8,9种操作下A,B,C,D,E,F,G,H,I各个时钟的操作方式
int num[9], start[9], linshi[9];//num记录每种操作各用了几次，start用于开始输入数据，linshi是start的副本
bool judge(int h[9])//判断是否9个时钟全为0（0即12）的函数
{
	for (int i = 0; i < 9; i++)
	{
		if (h[i])
		{
			return 0;
		}
	}
	return 1;
}
void dfs(int kind) 
{
	for (int i = 0; i < 9; i++)
	{
		linshi[i] = start[i];
	}//每次DFS开始的时候都要初始化，因为后面的2个for循环会全部跑一遍
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			linshi[i] = (linshi[i] + dir[j][i] * num[j]) % 4;//时钟只有0,1,2,3四种显示，linshgi自加该操作*该操作的个数
		}
	}
	if (judge(linshi))//如果全部为0了，输出操作过程
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < num[i]; j++)
			{
				cout << i + 1 << " ";
			}
		}
		return;
	}
	if (kind == 9)//没有第9种操作（操作数从0开始计算）
	{
		return;
	}
	for (int i = 0; i < 4; i++)//因为同一种操作操作4次等于没有操作，所以for循环里只有到3
	{
		num[kind] = i;//每种操作的个数
		dfs(kind + 1);//看下一种操作的DFS
	}
}
 int main() 
 {
	 for (int i = 0; i < 9; i++)
	 {
		 cin >> start[i];
	 }
	 dfs(0);
	 return 0;
 }