寫的有點冗:3
#include<iostream> #include<cstdlib> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 10000 #define ALP 1*2*3*4*5*6*7*8*9 #define N(x,y) (((y)-1)*3+(x)-1) #define SWAP(x,y) x^=y^=x^=y using namespace std; int Mts[10]={1,1,2,2*3,2*3*4, 2*3*4*5,2*3*4*5*6,2*3*4*5*6*7, 2*3*4*5*6*7*8,2*3*4*5*6*7*8*9}; bool step[ALP+1]; class Status { public: int I[9];int x,y;int Step; Status() { for(int lx=0;lx<9;lx++) I[lx]=9-lx; Step=0; x=3,y=3; } int CountPrm()const { int RE=0; for(int lx=0;lx<9;lx++) { int sum=0; for(int ly=lx+1;ly<9;ly++) sum+=(I[ly]<I[lx]); RE+=sum*Mts[9-lx-1]; } return RE+1; } }; istream& operator>>(istream &in,Status &ss) { for(int lx=0;lx<9;lx++) in >> ss.I[lx]; for(int lx=0;lx<9;lx++) if(ss.I[lx]==0) { ss.y=lx/3+1; ss.x=lx%3+1; ss.I[lx]=9; } return in; } ostream& operator<<(ostream &out,Status &ss) { for(int lx=0;lx<9;lx++) { out << ss.I[lx] << " "; if(lx%3==2) out << endl; } out << endl; out << "x=" << ss.x << " y=" << ss.y << endl; return out; } bool operator==(const Status &a1,const Status &b1) { for(int lx=0;lx<9;lx++) if(a1.I[lx]!=b1.I[lx]) return false; return true; } queue<Status> BFS; int main() { //Initializing memset(step,false,sizeof(step)); Status SStart,SEnd; cin >> SStart >> SEnd; //cout << SStart; BFS.push(SStart); if(SStart==SEnd){printf("0\n");return 0;} while(BFS.size()) { if(BFS.front()==SEnd) break; Status SS=BFS.front();BFS.pop(); //cout << SS; //getchar(); if(SS.x>=2) { Status Sa; Sa=SS;Sa.Step++; SWAP(Sa.I[N(Sa.x-1,Sa.y)],Sa.I[N(Sa.x,Sa.y)]); Sa.x--; if(step[Sa.CountPrm()]==false) { step[Sa.CountPrm()]=true; BFS.push(Sa); } } if(SS.x<=2) { Status Sa; Sa=SS;Sa.Step++; SWAP(Sa.I[N(Sa.x+1,Sa.y)],Sa.I[N(Sa.x,Sa.y)]); Sa.x++; if(step[Sa.CountPrm()]==false) { step[Sa.CountPrm()]=true; BFS.push(Sa); } } if(SS.y>=2) { Status Sa; Sa=SS;Sa.Step++; SWAP(Sa.I[N(Sa.x,Sa.y-1)],Sa.I[N(Sa.x,Sa.y)]); Sa.y--; if(step[Sa.CountPrm()]==false) { step[Sa.CountPrm()]=true; BFS.push(Sa); } } if(SS.y<=2) { Status Sa; Sa=SS;Sa.Step++; SWAP(Sa.I[N(Sa.x,Sa.y+1)],Sa.I[N(Sa.x,Sa.y)]); Sa.y++; if(step[Sa.CountPrm()]==false) { step[Sa.CountPrm()]=true; BFS.push(Sa); } } } printf("%d\n",BFS.front().Step); return 0; }
沒有留言:
張貼留言