poj 1077(八数码)

八数码问题有多种解法，本题解采用的是双向搜索
View Code
  1 #include<iostream>
  2 #include<map>
  3 #include<string>
  4 #include<queue>
  5 #include<stdio.h>
  6 #include<string.h>
  7 using namespace std;
  8 structnode{
  9  stringsx;
 10  int pos;
 11 };
 12 
 13 int dir[4]={-3,1,3,-1};
 14 char ch1[4]={'u','r','d','l'};
 15 char ch2[4]={'d','l','u','r'};
 16 int fact[9]={1,1,2,6,24,120,720,5040,40320};
 17 int b[500050]={0};
 18 stringsstr[500050];
 19 int hash(stringstr)
 20 {
 21     int sum=0;
 22     for(int i=1;str[i];i++)
 23     {
 24         int cnt=0;
 25         for(int j=0;j<i;j++)
 26         if(str[i]<str[j])cnt++;
 27         sum+=cnt*fact[i];
 28     }
 29     return sum;
 30 }
 31 stringbfs(stringstr)
 32 {
 33     memset(b,0,sizeof(b));
 34     queue<node>q1,q2;
 35     nodein;
 36     in.sx=str;
 37     for(int i=0;str[i];i++){if(str[i]=='9')in.pos=i;}
 38     q1.push(in);
 39     b[hash(str)]=1;
 40     in.sx="123456789";
 41     in.pos=8;
 42     q2.push(in);
 43     b[hash(in.sx)]=2;
 44     while(!q1.empty()&&!q2.empty())
 45     {
 46         nodeu=q1.front();
 47         q1.pop();
 48         int f=hash(u.sx);
 49         for(int i=0;i<4;i++)
 50         {
 51             nodev;
 52             v.pos=u.pos+dir[i];
 53             if((u.pos<3&&i==0)||(u.pos%3>1&&i==1)||
 54                (u.pos/3>1&&i==2)||(u.pos%3<1&&i==3))
 55             continue;
 56             v.sx=u.sx;
 57             v.sx[v.pos]=u.sx[u.pos];
 58             v.sx[u.pos]=u.sx[v.pos];
 59             int t=hash(v.sx);
 60             if(b[t]==1)continue;
 61             else if(b[t]==2)return sstr[f]+ch1[i]+sstr[t];
 62             sstr[t]=sstr[f]+ch1[i];
 63             b[t]=1;
 64             q1.push(v);
 65         }
 66         u=q2.front();
 67         q2.pop();
 68         f=hash(u.sx);
 69         for(int i=0;i<4;i++)
 70         {
 71             nodev;
 72             v.pos=u.pos+dir[i];
 73             if((u.pos<3&&i==0)||(u.pos%3>1&&i==1)||
 74                (u.pos/3>1&&i==2)||(u.pos%3<1&&i==3))
 75             continue;
 76             v.sx=u.sx;
 77             v.sx[v.pos]=u.sx[u.pos];
 78             v.sx[u.pos]=u.sx[v.pos];
 79             int t=hash(v.sx);
 80             if(b[t]==2)continue;
 81             else if(b[t]==1)return sstr[t]+ch2[i]+sstr[f];
 82             sstr[t]=ch2[i]+sstr[f];
 83             b[t]=2;
 84             q2.push(v);
 85         }
 86     }
 87     return "unslovable";
 88 }
 89 int main()
 90 {
 91     memset(b,0,sizeof(b));
 92     char s[110];
 93     while(gets(s))
 94     {
 95         stringstr="";
 96         for(int i=0;s[i];i++)
 97         {
 98             if(s[i]>='0'&&s[i]<='9')str=str+s[i];
 99             else if(s[i]=='x')str=str+'9';
100         }
101         int i=0;
102         cout<<bfs(str)<<endl;
103     }
104     return 0;
105 }