首页 > 代码库 > 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)