1 /*
   2 zju 1217
   3 HDu 1043
   4 ymc 2008/5/28
   5 解题思路:
   6 把x看作0,则每种状态对应012345678的一个排列。终止状态为123456780。
   7 012345678总共有有9!种排列,按照字典顺序给所有的排列排序,012345678在最前面,876543210在最后面。
   8 ptonum() 求出一个排列的序号
   9 numtop() 给出给定序号的排列
  10 从开始状态到终止状态BFS搜索 TLE
  11 反过来思BFS终止状态到所有状态的最短路径,对每次查询只要生成输出就可以
  12 */
  13 #include <iostream>
  14 #include <queue>
  15 using namespace std;
  16 const int Max=362880; //9!
  17 const int N=9;
  18 int f[N];
  19 int map[N]={1,2,3,4,5,6,7,8,0};
  20 int Trans[Max][4]; //记录各种状态间的转移,每种状态最多转移到四种状态。上下左右
  21 char Transop[Max][4];//各种状态转移的操作
  22 int start,end;
  23 struct Operator
  24 {
  25         int next;
  26         char op;
  27 };
  28 Operator OP[Max];  //其实状态到终止状态的最短路径以及操作(逆序)
  29 
  30 int ptonum(int a[])  //012345678的所有排列按照字典顺序排列,任意给出一个排列,计算在排列中的序号。
  31 {
  32         bool used[N];
  33         memset(used,0,sizeof(used));
  34         int ans=0;
  35         int num;
  36         for(int i=0;i<N;i++)
  37         {
  38                 num=0;
  39                 for(int j=0;j<a[i];j++)
  40                 {
  41                         if(!used[j])
  42                                 num++;
  43                 }
  44                 ans+=num*f[N-1-i];
  45                 used[a[i]]=true;
  46         }
  47         return ans;
  48 }
  49 void numtop(int a[],int num)//求给定序号的排列
  50 {
  51         bool used[N];
  52         memset(used,0,sizeof(used));
  53         int k;
  54         for(int i=0;i<N;i++)
  55         {
  56                 if(i!=N-1)
  57                 {
  58                         k=num/f[N-1-i];
  59                         num=num%f[N-1-i];
  60                 }
  61                 else
  62                         k=num;
  63                 int id=0;
  64                 int j;
  65                 for(j=0;j<N;j++)
  66                 {
  67                         if(!used[j])
  68                         {
  69                                 if(id==k)
  70                                         break;
  71                                 id++;
  72                         }
  73                 }
  74                 a[i]=j;
  75                 used[j]=true;
  76         }
  77 }
  78 void init() //主要求出所有的状态转移,以及对应的操作。
  79 {
  80         f[0]=0;
  81         f[1]=1;
  82         for(int i=2;i<N;i++)
  83                 f[i]=f[i-1]*i;
  84         end=ptonum(map);
  85         memset(Transop,'d',sizeof(Transop));
  86         int num,tmp,k,v;
  87         int b[N];
  88         for(int u=0;u<Max;u++)
  89         {
  90                 num=0;
  91                 numtop(b,u);
  92                 for(k=0;k<N;k++)
  93                         if(b[k]==0) break;
  94                 if(k>=3)  //x上移
  95                 {
  96                         tmp=b[k];b[k]=b[k-3];b[k-3]=tmp;
  97                         v=ptonum(b);
  98                         Trans[u][num]=v;
  99                         Transop[u][num]='d';
 100                         num++;
 101                         tmp=b[k];b[k]=b[k-3];b[k-3]=tmp;
 102                 }
 103                 if(k<6)  //x下移
 104                 {
 105                         tmp=b[k];b[k]=b[k+3];b[k+3]=tmp;
 106                         v=ptonum(b);
 107                         Trans[u][num]=v;
 108                         Transop[u][num]='u';
 109                         num++;
 110                         tmp=b[k];b[k]=b[k+3];b[k+3]=tmp;
 111                 }
 112                 if(k%3!=0)  //x左移
 113                 {
 114                         tmp=b[k];b[k]=b[k-1];b[k-1]=tmp;
 115                         v=ptonum(b);
 116                         Trans[u][num]=v;
 117                         Transop[u][num]='r';
 118                         num++;
 119                         tmp=b[k];b[k]=b[k-1];b[k-1]=tmp;
 120                 }
 121                 if(k%3!=2)  //x右移
 122                 {
 123                         tmp=b[k];b[k]=b[k+1];b[k+1]=tmp;
 124                         v=ptonum(b);
 125                         Trans[u][num]=v;
 126                         Transop[u][num]='l';
 127                         num++;
 128                         tmp=b[k];b[k]=b[k+1];b[k+1]=tmp;
 129                 }
 130 
 131         }
 132 }
 133 int Reverse(int a[N])
 134 {
 135         int sum=0;
 136         int b[N];
 137         memset(b,0,sizeof(b));
 138         for(int i=0;i<N;i++)
 139         {
 140                 for(int j=0;j<i;j++)
 141                         if(a[j]>a[i])
 142                                 b[a[i]]++;
 143                 sum+=b[a[i]];
 144         }
 145         return sum-b[0];
 146 }
 147 void PreBFS()
 148 {
 149         bool used[Max];
 150         memset(used,0,sizeof(used));
 151 //      start=ptonum(map);
 152         queue<int> q;
 153         q.push(end);
 154         used[end]=true;
 155         int u,v;
 156         while(!q.empty())
 157         {
 158                 u=q.front();
 159                 for(int i=0;Trans[u][i]!=0&&i<4;i++)
 160                 {
 161                         v=Trans[u][i];
 162                         if(!used[v])
 163                         {
 164                                 used[v]=true;
 165                                 OP[v].next=u;
 166                                 OP[v].op=Transop[u][i];
 167                                 q.push(v);
 168                         }
 169                 }
 170                 q.pop();
 171         }
 172 }
 173 void output()
 174 {
 175         int st=start;
 176         while(st!=end)
 177         {
 178                 cout<<OP[st].op;
 179                 st=OP[st].next;
 180         }
 181     cout<<endl;
 182 }
 183 
 184 int main()
 185 {
 186         init();
 187         PreBFS();
 188         char ch;
 189         while(cin>>ch)
 190         {
 191                 if(ch!='x')
 192                         map[0]=ch-'0';
 193                 else
 194                         map[0]=0;
 195                 for(int i=1;i<N;i++)
 196                 {
 197                         cin>>ch;
 198                         if(ch!='x')
 199                                 map[i]=ch-'0';
 200                         else
 201                                 map[i]=0;
 202                 }
 203                 int tmp=Reverse(map);
 204                 if(tmp%2!=0)
 205                 {
 206                         cout<<"unsolvable\n";
 207                         continue;
 208                 }
 209                 start=ptonum(map);
 210                 output();
 211         }
 212 }

hdu 1043参考答案 (last edited 2009-04-16 19:51:47 by 74)

ch3n2k.com | Copyright (c) 2004-2020 czk.