Gap HDU - 1067

 1 #include <iostream>
 2 #include <cstring>
 3 #include <unordered_map>
 4 #include <string>
 5 #include <map>
 6 #include <queue>
 7 using namespace std;
 8 const int N = 5,M = 10;
 9 string ed;
10 int tar[N][M],mp[N][M];
11 unordered_map<string,int> um;
12 void init()
13 {
14     int fl = 11;
15     for(int i=1;i<=4;i++)
16       for(int j=1;j<=7;j++)
17       {
18             tar[i][j] = fl++;
19             if(j==7) fl = (i+1)*10+1;
20       }
21     tar[1][8] = tar[2][8] = tar[3][8] = tar[4][8] = 1;
22     for(int i=1;i<=4;i++)
23       for(int j=1;j<=8;j++) ed+=tar[i][j];
24 }
25 void prework()
26 {
27     for(int i=1;i<=4;i++)
28       for(int j=2;j<=8;j++)
29         if(mp[i][j]%10==1)
30         {
31             int x = mp[i][j];
32             mp[x/10][1] = x;
33             mp[i][j] = 1;
34         }
35 }
36 int get(int x,string s)
37 {
38     for(int i=0;i<s.size();i++)
39       if(s[i]==x+1) return i;
40     return -1;
41 }
42 int bfs()
43 {
44     string st = "";
45     for(int i=1;i<=4;i++)
46       for(int j=1;j<=8;j++) st+=mp[i][j];
47     um[st] = 0;
48     queue<string> q;
49     q.push(st);
50     while(q.size())
51     {
52         string it = q.front();
53         q.pop();
54         if(it==ed) return um[it];
55         for(int i=0;i<32;i++)
56            if(it[i]==1)
57            {
58                  int idx = get(it[i-1],it);
59                  string v = it;
60                  swap(v[idx],v[i]);
61                  if(um.count(v)) continue;
62                  um[v] = um[it]+1;
63                  q.push(v);
64            }
65     }
66     return -1;
67 }
68 int main()
69 {
70     init();
71     int T;
72     scanf("%d",&T);
73     while(T--)
74     {
75         um.clear();
76         memset(mp,0,sizeof mp);
77         for(int i=1;i<=4;i++)
78           for(int j=2;j<=8;j++) scanf("%d",&mp[i][j]);
79         prework();
80         printf("%d\n",bfs()); 
81     }
82     return 0;
83 }