魔板问题，一道经典的康拓展开+BFS问题，为了实现方便，我用string类来表示字符串，此前很少用string类(因为不够高效，而且相对来说我对char数组的相关函数比较熟)，所以在这里也发现了很多容易被忽视的问题。
对于康拓展开不太熟系的可以先参看一篇博客：http://blog.csdn.net/zhongkeli/article/details/6966805
关于sting类，大家要注意，在赋值的时候，其赋值位置不能与首位置间存在未赋值部分。
题目需要转换思路的地方是: 我们需要将起始魔板->目标魔板 转换为 标准魔板->新目标魔板的形式，以便离线(打表)一次就够了。
具体代码如下：
1 //魔板问题-BFS(离线)+康拓展开 2 //Time: 38Ms Memory:6484K 3 #include<iostream> 4 #include<string> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 9 #define MAX 40321 10 11 int fac[8] = { 1,1,2,6,24,120,720,5040 }; //阶乘数组 12 13 int v[MAX]; //访问标记 14 string ans[MAX]; //离线表 15 16 struct Board{ 17 int val; //Hash值 18 string str; 19 }; 20 21 //康拓展开(Hash) 22 int Contor(string str) 23 { 24 int num = 0; //Hash值 25 for (int i = 0; i < 8; i++) 26 { 27 int tmp = 0; //在此后的序列中的位置(升序) 28 for (int j = i + 1; j < 8; j++) 29 if (str[j] < str[i]) tmp++; 30 num += tmp*fac[7 - i]; 31 } 32 return num; 33 } 34 35 //离线打表(BFS) 36 void Init() 37 { 38 queue<Board>Q; 39 Board t, tmp; 40 t.str = tmp.str = "12345678"; //初始数组 41 t.val = Contor(t.str); 42 v[t.val] = 1; 43 Q.push(t); 44 while (!Q.empty()) { 45 t = Q.front(); 46 Q.pop(); 47 48 // A:交换行 49 for (int i = 0; i < 8; i++) 50 tmp.str[(i + 4) % 8] = t.str[i]; 51 52 tmp.val = Contor(tmp.str); 53 if (!v[tmp.val]) { 54 v[tmp.val] = 1; 55 ans[tmp.val] = ans[t.val] + 'A'; 56 Q.push(tmp); 57 } 58 59 // B:循环右移 60 for (int i = 0; i < 4; i++) 61 tmp.str[(i + 1) % 4] = t.str[i]; 62 for (int i = 4; i < 8; i++) 63 tmp.str[(i + 1) % 4 + 4] = t.str[i]; 64 65 tmp.val = Contor(tmp.str); 66 if (!v[tmp.val]) { 67 v[tmp.val] = 1; 68 ans[tmp.val] = ans[t.val] + 'B'; 69 Q.push(tmp); 70 } 71 72 // C:中心顺时旋转 73 tmp.str = t.str; 74 tmp.str[1] = t.str[5]; tmp.str[2] = t.str[1]; 75 tmp.str[6] = t.str[2]; tmp.str[5] = t.str[6]; 76 77 tmp.val = Contor(tmp.str); 78 if (!v[tmp.val]) { 79 v[tmp.val] = 1; 80 ans[tmp.val] = ans[t.val] + 'C'; 81 Q.push(tmp); 82 } 83 } 84 } 85 86 int main() 87 { 88 Init(); //BFS 89 string ts, te; 90 while (cin >> ts >> te) 91 { 92 /*转换成顺序魔板*/ 93 swap(ts[5], ts[6]); 94 swap(ts[4], ts[7]); 95 swap(te[5], te[6]); 96 swap(te[4], te[7]); 97 98 /*将起始魔板转换为标准魔板，相应目标魔板也进行变更*/ 99 char tmp[9]; 100 for (int i = 0; i < 8; i++) 101 tmp[ts[i] - '0'] = i + '1'; 102 for (int i = 0; i < 8; i++) 103 te[i] = tmp[te[i] - '0']; 104 105 cout << ans[Contor(te)] << endl; 106 } 107 108 return 0; 109 }