Eight II HDU - 3567

  1 #include <iostream> 
  2 #include <cstring>
  3 #include <string>
  4 #include <vector>
  5 #include <queue>
  6 #include <algorithm>
  7 using namespace std;
  8 typedef long long LL;
  9 const int N = 10,M = 362890,INF = 0x3f3f3f3f;
 10 char stt[N],edd[N];
 11 int st[N],ed[N],tmp[N],dist[2][M];
 12 int xx[4] = {1,0,0,-1},yy[4] = {0,-1,1,0};
 13 LL path[2][M],pow4[35];
 14 string ans;
 15 int minv;
 16 char index[N] = "dlru";
 17 int factor[12] = {1,1,2,6,24,120,720,5040,40320,362880,3628000};
 18 struct Node{
 19     int step,val;
 20     void operator=(const Node& s){
 21         this->step = s.step;
 22         this->val = s.val;
 23     }
 24 };
 25 int cantor(int a[])
 26 {
 27     int res = 0;
 28     for(int i=0;i<9;i++)
 29     {
 30         int small = 0;
 31         for(int j=i+1;j<9;j++)
 32            if(a[i]>a[j]) small++;
 33         res+=small*factor[8-i];
 34     }
 35     return res+1;
 36 }
 37 int get(int a[])
 38 {
 39     for(int i=0;i<9;i++)
 40       if(!a[i]) return i;
 41     return -1;
 42 }
 43 void decantor(int a[],int val)
 44 {
 45     vector<int> v;
 46     for(int i=0;i<9;i++) v.push_back(i);
 47     for(int i=0;i<9;i++)
 48     {
 49         int cnt = val/factor[8-i];
 50         int now = val%factor[8-i];
 51         val = now;
 52         sort(v.begin(),v.end());
 53         a[i] = v[cnt];
 54         v.erase(v.begin()+cnt);
 55     }
 56 }
 57 string Get_Str(int op,LL pows,int val)
 58 {
 59     int step = dist[op][val];
 60     int str[100];
 61     for(int i=1;i<=step;i++)
 62     {
 63         str[i] = pows%4;
 64         pows/=4ll;
 65     }
 66     string ans = "";
 67     for(int i=step;i>=1;i--)
 68         ans +=index[str[i]];
 69     return ans;
 70 }
 71 bool extend(queue<Node>& q,int op)
 72 {
 73     Node itt = q.front();
 74     q.pop();
 75     LL sum;
 76     int it = itt.val; int step = itt.step;
 77     decantor(tmp,it-1);
 78     int idx = get(tmp);
 79     int x = idx/3,y = idx%3;
 80     for(int i=0;i<4;i++)
 81     {
 82         int dx = x+xx[i],dy = y+yy[i];
 83         if(dx>=0&&dx<3&&dy>=0&&dy<3)
 84         {
 85             int now = dx*3+dy;
 86             swap(tmp[now],tmp[idx]);
 87             int val = cantor(tmp);
 88             swap(tmp[now],tmp[idx]);
 89             if(op) sum = path[op][it]*4+i;
 90             else sum = (3-i)*pow4[step]+path[op][it];
 91             if(dist[op][val]<INF)//此方向已经遍历了 
 92             {
 93                 if(step+1>dist[op][val]) continue;
 94                 else dist[op][val] = step+1;
 95                 if(sum<path[op][val]) path[op][val] = sum;
 96             }else{//没来过 
 97                 dist[op][val] = step+1;
 98                 path[op][val] = sum;
 99             }
100             Node news;
101             news.step = step+1; news.val = val;
102             if(dist[op^1][val]<INF)
103             {
104                 string s = Get_Str(1,path[1][val],val)+Get_Str(0,path[0][val],val);
105         //        cout<<s<<endl;
106                 if(s.size()>minv)
107                 {
108                     printf("%d\n%s\n",minv,ans.c_str());
109                     return 1;
110                 }else if(s.size()<minv) minv = s.size(),ans = s;
111                 else if(s<ans) ans = s;
112             }
113             q.push(news);
114         }
115     }
116     return 0;
117 }
118 void bfs()
119 {
120     queue<Node> q1,q2;
121     int sv = cantor(st),ev = cantor(ed);
122     if(sv==ev) {printf("0\n\n");return;}
123     Node s; s.step = 0,s.val = sv;
124     Node e; e.step = 0,e.val = ev;
125     q1.push(s); dist[1][s.val] = 0; 
126     q2.push(e); dist[0][e.val] = 0;
127     while(q1.size()&&q2.size())
128     {
129         bool ok = 0;
130         if(q1.size()<=q2.size()) ok = extend(q1,1);
131         else ok = extend(q2,0);
132         if(ok) return;
133     }
134 }
135 void init()
136 {
137     pow4[0] = 1;
138     for(int i=1;i<=30;i++) 
139       pow4[i] = pow4[i-1]*4ll;
140 }
141 int main()
142 {
143     int T,kcase = 0;
144     init();
145     scanf("%d",&T);
146     while(T--)
147     {
148         memset(dist,0x3f,sizeof dist);
149         memset(path,0,sizeof path);
150         minv = INF;
151         scanf("%s%s",stt,edd);
152         printf("Case %d: ",++kcase);
153         for(int i=0;i<9;i++)
154           if(stt[i]==‘X‘) st[i] = 0;
155           else st[i] = stt[i]-‘0‘;
156         for(int i=0;i<9;i++)
157           if(edd[i]==‘X‘) ed[i] = 0;
158           else ed[i] = edd[i]-‘0‘; 
159         bfs();
160     }
161     return 0;
162 }