|
|
 #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)!=0) continue;
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;
}
};
|