HDU 1430 魔板

思路：

初态a和末态b经过相同的一系列操作，使初态a变成12345678，同时得到新的末态c，然后只需要求12345678到末态c的变换步骤即为初态a到末态b的变换步骤。所以，只要把12345678的所有可达状态遍历一次并记录下变换步骤即可。

 1 #include <cstdio>
 2 #include <string.h>
 3 #include <stack>
 4 using namespace std;
 5 const int MAX = 40500, fact[] = {1, 1, 2, 6, 24, 120, 720, 5040}, Move[3][8] = {{7, 6, 5, 4, 3, 2, 1, 0}, {3, 0, 1, 2, 5, 6, 7, 4}, {0, 6, 1, 3, 4, 2, 5, 7}};
 6 bool vis[MAX] = {0};
 7 int LOG[MAX][8] = {1, 2, 3, 4, 5, 6, 7, 8};
 8 struct node
 9 {
10     char MOVE;
11     int father;
12 }path[MAX];
13 bool TryToInsert(int Front, int Rear, int MOVE)
14 {
15     int Fcode = 0, Rcode = 0, i, j, cnt;
16     for(i=0; i<7; ++i)
17     {
18         cnt = 0;
19         for(j=i+1; j<8; ++j)
20             if(LOG[Rear][i] > LOG[Rear][j])
21                 ++cnt;
22         Rcode += cnt * fact[7-i];
23     }
24     if(vis[Rcode])
25         return false;
26     else
27     {
28         for(i=0; i<7; ++i)
29         {
30             cnt = 0;
31             for(j=i+1; j<8; ++j)
32                 if(LOG[Front][i] > LOG[Front][j])
33                     ++cnt;
34             Fcode += cnt * fact[7-i];
35         }
36         path[Rcode].father = Fcode;
37         path[Rcode].MOVE = 'A' + MOVE;
38         return vis[Rcode] = true;
39     }
40 }
41 void BFS(void)
42 {
43     vis[0] = true;
44     int Front = 0, Rear = 1, i, j;
45     do
46     {
47         for(i=0; i<3; ++i)
48         {
49             for(j=0; j<8; ++j)
50                 LOG[Rear][j] = LOG[Front][ Move[i][j] ];
51             if(TryToInsert(Front, Rear, i))
52                 ++Rear;
53         }
54         ++Front;
55     } while (Front < Rear);
56 }
57 int main(void)
58 {
59     BFS();
60     stack<char> s;
61     int Start[8], End[8], Aim[8], AimCode, i, j, cnt;
62     char StartStr[10], EndStr[10];
63     while(~scanf("%s%s", StartStr, EndStr))
64     {
65         for(i=0; i<8; ++i)
66         {
67             Start[i] = StartStr[i] - '0';
68             End[i] = EndStr[i] - '0';
69         }
70         for(i=0; i<8; ++i)
71         {
72             for(j=0; End[i] != Start[j]; ++j);
73             Aim[i] = j+1;
74         }
75         AimCode = 0;
76         for(i=0; i<7; ++i)
77         {
78             cnt = 0;
79             for(j=i+1; j<8; ++j)
80                 if(Aim[i] > Aim[j])
81                     ++cnt;
82             AimCode += cnt * fact[7-i];
83         }
84         while(AimCode)
85         {
86             s.push(path[AimCode].MOVE);
87             AimCode = path[AimCode].father;
88         }
89         while(!s.empty())
90         {
91             printf("%c", s.top());
92             s.pop();
93         }
94         printf("
");
95     }
96 }