随笔-141  评论-9  文章-3  trackbacks-0

/*
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 小阮 阅读(203) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理