|
#include <iostream>
#include <set>
#include <string>
#include <queue>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct state {
long a;
long b;
long c;
state(long i,long j,long k):a(i),b(j),c(k)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {}
};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct peg {
state s;
int c;
peg(state z,int cc):s(z),c(cc)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {}
};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool operator==(const state& a,const state& b) {
return a.a==b.a&&a.b==b.b&&a.c==b.c;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
set<state> vis;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) long conv(const string& a) {
long r=0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=0;i<a.size();i++) {
r=r*4+(a[i]-'A'+1);
}
return r;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) class HanoiTower {
public:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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));
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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));
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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;
}
};
|