Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

topcoder学习中

#include <iostream>
#include 
<set>
#include 
<string>
#include 
<queue>
using namespace std;

struct state{
    
long a;
    
long b;
    
long c;
    state(
long i,long j,long k):a(i),b(j),c(k)
    
{}
}
;
struct peg{
    state s;
    
int c;
    peg(state z,
int cc):s(z),c(cc)
    
{}
}
;
bool operator==(const state& a,const state& b){
    
return a.a==b.a&&a.b==b.b&&a.c==b.c;
}

bool operator<(const state& a,const state& b){
    
if(a.a!=b.a) return a.a<b.a;
    
if(a.b!=b.b) return a.b<b.b;
    
return a.c<b.c;
}


set<state> vis;

long conv(const string& a){
    
long r=0;
    
for(int i=0;i<a.size();i++){
        r
=r*4+(a[i]-'A'+1);
    }

    
return r;
}


class HanoiTower{
public:
    
int moves(string pegA,string pegB,string pegC){
        
int r=0;
        queue
<peg> q;
        q.push( peg( state( conv(pegA),conv(pegB),conv(pegC) ), 
0 ) );
        
int numA=0,numB=0,numC=0;
        
string big=pegA+pegB+pegC;
        
for(int i=0;i<big.size();i++){
            
if(big[i]=='A') numA++;
            
else if(big[i]=='B') numB++;
            
else numC++;
        }

        
string tA=string(numA,'A'),tB=string(numB,'B'),tC=string(numC,'C');
        state target
=state(conv(tA),conv(tB),conv(tC));
        
while(!q.empty()){
            peg z
=q.front();q.pop();
            
if(z.s==target) return z.c;
            
if(vis.count(z.s)!=0continue;
            vis.insert(z.s);
            
long aa=z.s.a;
            
long bb=z.s.b;
            
long cc=z.s.c;
            
if(aa>0){
                
int m=aa%4;
                q.push( peg( state((aa
-m)/4,bb*4+m,cc),z.c+1));
                q.push( peg( state((aa
-m)/4,bb,cc*4+m),z.c+1));
            }
        
            
if(bb>0){
                
int m=bb%4;
                q.push( peg( state(aa
*4+m,(bb-m)/4,cc),z.c+1));
                q.push( peg( state(aa,(bb
-m)/4,cc*4+m),z.c+1));
            }
        
            
if(cc>0){
                
int m=cc%4;
                q.push( peg( state(aa,bb
*4+m,(cc-m)/4),z.c+1) );
                q.push( peg( state(aa
*4+m,bb,(cc-m)/4),z.c+1) );
            }

        }

        
return r;
    }

}
;

posted on 2009-08-14 12:17 Drolca 阅读(153) 评论(1)  编辑 收藏 引用

评论

# re: topcoder学习中  回复  更多评论   

...麻烦了...
2009-08-14 22:08 | Drolva

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