/**//*
ID: lorelei3
TASK: clocks
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
char *movestr[] =
{"abde","abc","bcef","adg","bdefh","cfi","degh","ghi","efhi"};
int movedist[9][9];
int clocks[9];
int move[9];
int bestmove[9];
int nbestmove;
void mkmove(){
int i;
char *p;
for(i=0; i<9; ++i)
for(p=movestr[i]; *p; p++)
movedist[i][*p-'a']=3;
}
void solve(int k){
int i,j,n,rep;
if(k==9){
for(j=0; j<9; ++j)
if(clocks[j]%12!=0)
return;
n=0;
for(j=0; j<9; ++j)
n+=move[j];
if(nbestmove==0 || n<nbestmove){
nbestmove = n;
for(j=0; j<9; ++j)
bestmove[j] = move[j];
}
return;
}
for(rep=3; rep>=0; --rep){
for(i=0; i<rep; ++i)
for(j=0; j<9; ++j)
clocks[j] += movedist[k][j];
move[k]=rep;
solve(k+1);
for(i=0; i<rep; ++i)
for(j=0; j<9; ++j)
clocks[j] -= movedist[k][j];
}
}
int main(){
char *ch="";
int i,j;
ifstream in("clocks.in");
ofstream out("clocks.out");
for(i=0;i<9;i++)
in>>clocks[i];
mkmove();
solve(0);
for(i=0; i<9; ++i)
for(j=0; j<bestmove[i]; ++j){
out<<ch<<i+1;
ch=" ";
}
out<<endl;
return 0;
}posted on 2010-11-09 12:53
小阮 阅读(182)
评论(0) 编辑 收藏 引用 所属分类:
USACO