首页 > 代码库 > hdu 1043 eight(poj 1077) (bfs)
hdu 1043 eight(poj 1077) (bfs)
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef int State[9];const int MAXSTATE=1000000;State st[MAXSTATE],goal;//int dist[MAXSTATE];int vis[362880],fact[9];const int dx[]={-1,1,0,0}; //u d l r //d u r lconst int dy[]={0,0,-1,1};struct father{ int nfa; char op;};father fa[MAXSTATE];void init_lookup_table() //初始化查找表{ fact[0]=1; for(int i=1;i<9;i++) fact[i]=fact[i-1]*i;}int try_to_insert(int s){ int code=0; for(int i=0;i<9;i++) { int cnt=0; for(int j=i+1;j<9;j++) if(st[s][j]<st[s][i]) cnt++; code+=fact[8-i]*cnt; } if(vis[code]) return 0; return vis[code]=1;}int find_id(int s){ int code=0; for(int i=0;i<9;i++) { int cnt=0; for(int j=i+1;j<9;j++) if(st[s][j]<st[s][i]) cnt++; code+=fact[8-i]*cnt; } return code;}void bfs(){ init_lookup_table(); int front=1,rear=2,z; int idfront=find_id(front); vis[idfront]=1; fa[idfront].nfa=-1; while(front<rear) { //printf("%d %d..\n",front,rear); State& s=st[front]; idfront=find_id(front); for(z=0;z<9;z++) if(!s[z])break;//查找 0 的位置 int x=z/3,y=z%3; for(int d=0;d<4;d++) //d u r l { int newx=x+dx[d]; int newy=y+dy[d]; int newz=newx*3+newy; if(newx>=0&&newx<3&&newy>=0&&newy<3) { State & t=st[rear]; memcpy(&t,&s,sizeof(s)); t[newz]=s[z]; t[z]=s[newz]; /*for(int ii=0;ii<9;ii++) { printf("%d ",t[ii]); } printf("\n");*/ if(try_to_insert(rear)) { int idrear=find_id(rear); fa[idrear].nfa=idfront; //printf("%d %d...\n",rear,idrear); if(d==0) //d u r l { fa[idrear].op=‘d‘; } else if(d==1) { fa[idrear].op=‘u‘; } else if(d==2) { fa[idrear].op=‘r‘; } else if(d==3) { fa[idrear].op=‘l‘; } rear++; } } } front++; }}int main(){ //freopen("out.txt","w",stdout); int i; char temp; memset(fa,0,sizeof(fa)); memset(vis,0,sizeof(vis)); for(i=1;i<=8;i++) st[1][i-1]=i; st[1][8]=0; bfs(); while(cin>>temp) { if(temp!=‘x‘) goal[0]=temp-‘0‘; else goal[0]=0; for(i=1;i<9;i++) { cin>>temp; if(temp!=‘x‘) goal[i]=temp-‘0‘; else goal[i]=0; } int code=0; for(int i=0;i<9;i++) { int cnt=0; for(int j=i+1;j<9;j++) if(goal[j]<goal[i]) cnt++; code+=fact[8-i]*cnt; } if(fa[code].nfa==0) printf("unsolvable\n"); else { int now=code; while(1) { if(now==0) {printf("\n");break;} printf("%c",fa[now].op); now=fa[now].nfa; } } } return 0;}
hdu 1043 eight(poj 1077) (bfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。