4次同一操作等效于沒有操作，操作的順序不影響結(jié)果。
用迭代加深搜索解(貌似效率不高)，代碼如下：
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("clocks.in");
ofstream fout("clocks.out");
#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif
//op[i][j]為操作i對(duì)第j個(gè)時(shí)鐘增加的小時(shí)數(shù)
int ops[9][9];
string op[9] = {
"ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"
};
//clocks當(dāng)前時(shí)鐘的狀態(tài)
int clocks[9];
//當(dāng)前的操作序列
int cur_ops[9];
void pre()
{
memset(ops,0,sizeof(ops) );
memset(cur_ops,0,sizeof(cur_ops));
for(int i=0;i<9;++i){
for(int j=0;j<op[i].size();++j){
ops[i][op[i][j]-'A'] = 3;
}
}
}
//執(zhí)行clocks操作序列
void do_ops()
{
for(int i=0;i<9;++i){
if(cur_ops[i]!=0)
for(int j=0;j<9;++j){
clocks[j]+=ops[i][j]*cur_ops[i];
clocks[j]%=12;
}
}
}
//i為當(dāng)前到達(dá)的操作編號(hào)
void dfs(int i, int cur_depth,int max_dep)
{
//到達(dá)迭代加深搜索的最大深度或i超過最大
if(cur_depth>max_dep||i>9)
return;
if(cur_depth==max_dep){
//保存當(dāng)前clocks狀態(tài)
int saved[9];
memcpy(saved,clocks,sizeof(clocks));
do_ops();
bool valid = true;
for(int i=0;i<9;++i){
if(clocks[i]!=0){
valid = false;
break;
}
}
if(valid){
//時(shí)鐘全為0，到達(dá)可行解
bool first = true;
for(int i=0;i<9;++i){
if(cur_ops[i]!=0){
int t = cur_ops[i];
while(t--){
if(first){
out<<i+1;
first = false;
}else{
out<<" "<<i+1;
}
}
}
}
out<<endl;
exit(0);
}else{
//恢復(fù)時(shí)鐘
memcpy(clocks,saved,sizeof(saved));
return;
}
}
for(int inc=3;inc>=0;inc--){
//因?yàn)橐笞钚〉男蛄校瑑?yōu)先多分配當(dāng)前i,再分配后續(xù)更大的號(hào)
if(cur_depth+inc<=max_dep&&cur_ops[i]+inc<4){
cur_ops[i]+=inc;
dfs(i+1,cur_depth+inc,max_dep);
cur_ops[i]-=inc;
}
}
}
void solve()
{
pre();
for(int i=0;i<9;++i){
in>>clocks[i];
clocks[i]%=12;
}
for(int d = 0;d<=3*9;++d){
dfs(0,0,d);
}
}
int main(int argc,char *argv[])
{
solve();
return 0;
}