Eight HDU - 1043

 1 #include <unordered_map>
 2 #include <iostream> 
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <string>
 6 #include <queue>
 7 using namespace std;
 8 const int N = 362890,M = 10;
 9 char index[5] = "durl";
10 int vis[N],temp[M],b[M];
11 int xx[4] = {-1,1,0,0},yy[4] ={0,0,-1,1};
12 int factor[12] = {1,1,2,6,24,120,720,5040,40320,362880,3628000};
13 unordered_map<int,string> path;
14 int cantor(int a[])//康拓展开 
15 {
16     int sum = 0;
17     for(int i=0;i<9;i++)
18     {
19         int small = 0;
20         for(int j=i+1;j<9;j++)
21            if(a[i]>a[j]) small++;
22         sum+=small*factor[8-i];
23     }
24     return sum+1;
25 }
26 void decantor(int a[],int val)
27 {
28     vector<int> v;
29     for(int i=0;i<9;i++) v.push_back(i);
30     for(int i=0;i<9;i++)
31     {
32         int cnt = val/factor[8-i];
33         int now = val%factor[8-i];
34         val = now;
35         sort(v.begin(),v.end());
36         a[i] = v[cnt];
37         v.erase(v.begin()+cnt);
38     }
39 }
40 int get(int a[])
41 {
42     for(int i=0;i<9;i++)
43       if(a[i]==0) return i;
44     return -1;
45 }
46 void bfs()
47 {
48     for(int i=0;i<8;i++) temp[i] = i+1;
49     temp[8] = 0;
50     queue<int> q;
51     int vw = cantor(temp);
52     q.push(vw);
53     path[vw] = "";
54     vis[vw] = 1;
55     while(q.size())
56     {
57         int it = q.front();
58         q.pop();
59         decantor(temp,it-1);
60         int pos = get(temp);
61         int x = pos/3,y = pos%3;
62     //    memcpy(b,temp,sizeof b);
63         for(int i=0;i<4;i++)
64         {
65             int dx = x+xx[i],dy = y+yy[i];
66             if(dx>=0&&dx<3&&dy>=0&&dy<3)
67             {
68                 int spos = dx*3+dy;
69                 swap(temp[pos],temp[spos]);
70                 int val = cantor(temp);
71                 swap(temp[pos],temp[spos]);
72                 if(vis[val]) continue;
73                 vis[val] =1;
74                 path[val] = index[i]+path[it];
75                 q.push(val);
76             }
77         }
78     }
79 }
80 int main()
81 {
82     bfs();
83     string ns;
84     while(getline(cin,ns))
85     {
86         int cnt = 0;
87         for(int i=0;i<ns.size();i++)
88            if(isalnum(ns[i]))
89            {
90                    if(ns[i]==‘x‘) b[cnt++] = 0;
91                 else b[cnt++] = ns[i]-‘0‘;
92            }
93         int val = cantor(b);
94         if(!vis[val]) puts("unsolvable");
95         else printf("%s\n",path[val].c_str());
96     }
97     return 0;
98 }