卢俊达

题目大意：

给出9个表盘和9种表针操作方法，要求找出一个能使所有表针都指向12点的方案。

思路：

用深搜遍历所有可能方案即可，具体思路见代码。

代码：

/*
ID: lujunda1
LANG: C++
PROG: clocks
*/
#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
struct state
//定义结构体来表示当前时钟的状态。mark[]记录各方法使用的数量。 
{
	int clock[3][3];
	int mark[9];
};
bool check(state temp)
//通过temp的clock[]判断temp状态下的表针是否全部指向12点。 
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(temp.clock[i][j]%12)
				return false;
	return true;
}
void output(state temp)
//输出temp状态下的方法序列。 
{
	bool check=true;
	for(int i=0;i<9;i++)
		for(int j=0;j<temp.mark[i];j++)
			if(check)
			{
				printf("%d",i+1);
				check=false;
			}
			else
				printf(" %d",i+1);
	printf("\n");
}
int operation[9][9]=
//operation[][]是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}
};
state op(state temp,int n)
//op()方法的含义是，计算temp状态在i方法作用后的结果并返回。 
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(operation[n][i*3+j])
				temp.clock[i][j]+=3;
	temp.mark[n]++;
	return temp;
}
int pos(state temp)
//这实际是为避免重复运算而定义的步骤。
//当方法序列为111222334，保证其递归下的序列为1112223344而不是1112223334。
//因为1112223334在111222334之前就已经出现过。 
{
	for(int i=8;i>=0;i--)
	//返回使用次数不为0且序号最大的方法的序号。 
		if(temp.mark[i]>0)
			return i;
	return 0;
}
bool dfs(state temp)
//深搜 
{
	if(check(temp))
	//优先检查temp状态 
	{
		output(temp);
		return true;
	}
	for(int i=pos(temp);i<9;i++) 
		if(temp.mark[i]<3&&dfs(op(temp,i)))
		//temp.mark[i]<3保证了每个方法使用不超过4次，超过4次无意义（指针转了超过一圈）。 
			return true;
	return false;
}
int main()
{
	freopen("clocks.in","r",stdin);
	freopen("clocks.out","w",stdout);
	state original;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			scanf("%d",&original.clock[i][j]);
	for(int i=0;i<9;i++)
		original.mark[i]=0;
	dfs(original);
}