bashuma.cpp.zip_ bashuma.cpp

#include <iostream> #include <queue> #include <set> #include <fstream> #include <string> #include <sstream> #include <vector> #include "math.h" using namespace std; typedef struct state { int s[3][3]; int f,g,h; char move_from; public: state(int p[3][3]) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) this->s[i][j]=p[i][j]; } state() { } void print_state() { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) cout<<this->s[i][j]<<" "; cout<<endl; } } void calculate_h() { int m,n; this->h=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(s[i][j]) { m=s[i][j]/3; n=s[i][j]%3-1; this->h+=abs(i-m)+abs(j-n); } else { this->h+=abs(i-2)+abs(j-2); } } } } state *pre; }state; typedef struct _tagcompare { bool operator() (const state &a, const state &b) { if(a.f>b.f) { return true; } else { if((a.f == b.f)&& (a.h > b.h)) {return true;} else { if(a.f < b.f) {return false;} if((a.h==b.h)&&(a.g > b.g)) {return true;} else {return false;} } } } }compare; typedef struct _equal { public: bool operator() (const state &a,const state &b) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(a.s[i][j]!=b.s[i][j]) return true; } } return false; } }noequalto; typedef priority_queue< state ,vector<state>,compare > pri_q; pri_q state_q; typedef set< state,noequalto > s_set; s_set state_set; void move(state &current,char m) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if( current.s[i][j]==0 ) { switch(m) { case 'n': current.s[i][j]=current.s[i-1][j]; current.s[i-1][j]=0; break; case 's': current.s[i][j]=current.s[i+1][j]; current.s[i+1][j]=0; break; case 'w': current.s[i][j]=current.s[i][j-1]; current.s[i][j-1]=0; break; case 'e': current.s[i][j]=current.s[i][j+1]; current.s[i][j+1]=0; break; } return; } } } return; } bool can_move(int p[3][3],char m) { switch(m) { case 'n': if( p[0][0]!=0 && p[0][1]!=0 && p[0][2]!=0 ) return true; else return false; break; case 's': if( p[2][0]!=0 && p[2][1]!=0 && p[2][2]!=0 ) return true; else return false; break; case 'w': if( p[0][0]!=0 && p[1][0]!=0 && p[2][0]!=0 ) return true; else return false; break; case 'e': if( p[0][2]!=0 && p[1][2]!=0 && p[2][2]!=0 ) return true; else return false; break; default: break; } } vector<state> state_vector; int search(state &); bool isFinished(const state &); void print_path() { for(vector<state>::iterator it = state_vector.begin();it != state_vector.end();it++) { if(it->move_from != '0') cout<<it->move_from<<endl; it->print_state(); //cout<<endl; } } int main() { string pos,ss; ifstream in("bashuma.txt"); int i=0,j=0; state current; while(getline(in,ss)) { istringstream stream(ss); j=0; while(stream>>pos) { current.s[i][j]=atoi(pos.c_str()); j++; } i++; } current.move_from='0'; //current.print_state(); if( isFinished(current) ) { current.print_state(); } else { search(current); print_path(); state_set.clear(); //state_q.clear(); state_vector.clear(); } cin>>ss; return 0; } bool not_exist(state &current) { int quto; quto=state_set.size(); state_set.insert(current); if( quto==state_set.size() ) return false; else return true; } bool isFinished(const state &current) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if( current.s[i][j] != 0 ) if( current.s[i][j] != i*3+j+1 ) return false; else continue; else if( i!=2 || j!=2 ) return false; else continue; return true; } int search(state &current) { state next; state_vector.push_back(current); for(int i=-1;i<=1;i++) { for(int j=-1;j<=1;j++) { if( i == -1 && j == 0 ) { if(can_move(current.s,'n')) { state temp(current.s); move(temp,'n'); state set_temp(temp.s); if( not_exist( set_temp ) ) { temp.pre=&current; temp.calculate_h(); temp.g=current.g+1; temp.f=temp.g+temp.h; temp.move_from='n'; if( isFinished(temp) ) { state_vector.push_back(temp); return 0; } else state_q.push(temp); } } } else if( i == 0 && j ==-1 ) { if(can_move(current.s,'w')) { state temp(current.s); move(temp,'w'); state set_temp(temp.s); if( not_exist( set_temp ) ) { temp.pre=&current; temp.calculate_h(); temp.g=current.g+1; temp.f=temp.g+temp.h; temp.move_from='w'; if(isFinished(temp)) { state_vector.push_back(temp); return 0; } else state_q.push(temp); } } } else if( i == 0 && j == 1 ) { if(can_move(current.s,'e'))