对于该题可以直接预处理初始状态[0, 1, 2, 3, 4, 5, 6, 7]所有可以到达的状态,保存到达的路径,直接打印答案即可。
关于此处的状态转换:假设有初始状态为2,3,4,5,0,6,7,1,目标状态为7,1,4,5,2,3,0,6,首先把初态看做0,1,2,3,4,5,6,7,那么目标状态应该看做6,7,2,3,0,1,4,5直接查询到达状态6,7,2,3,0,1,4,5的路径即可。
PS:hdu3567与这题类似。
AC代码:93ms
#include<cstdio> #include<cstring> #include<queue> #include<string> #include<iostream> #include<algorithm> using namespace std; typedef int state[8]; const int maxn = 45000; int vis[maxn]; string path[maxn]; int op[][8] = { 4, 5, 6, 7, 0, 1, 2, 3, 3, 0, 1, 2, 7, 4, 5, 6, 0, 5, 1, 3, 4, 6, 2, 7 }; char dir[] = {'A', 'B', 'C'}; int st[] = {0, 1, 2, 3, 4, 5, 6, 7}; int fact[8]; void deal() { //1~8阶乘打表,方便编码 fact[0] = 1; for(int i = 1; i < 8; ++i) fact[i] = fact[i - 1] * i; } int KT(int *a) { //康托 int code = 0; for(int i = 0; i < 8; ++i) { int cnt = 0; for(int j = i + 1; j < 8; ++j) if(a[j] < a[i]) cnt++; code += fact[7 - i] * cnt; } return code; } struct node{ int a[8]; int code; node(){ } node(int *b, int code):code(code) { memcpy(a, b, sizeof(a)); } }; void walk(int c, int *a) { //对数组进行第c种操作 int b[8]; memcpy(b, a, sizeof(b)); for(int i = 0; i < 8; ++i) { a[i] = b[op[c][i]]; } } void bfs() { //预处理所有可以到达的状态 memset(vis, 0, sizeof(vis)); int code = KT(st); vis[code] = 1; path[code] = ""; queue<node>q; q.push(node(st, code)); while(!q.empty()){ node p = q.front(); q.pop(); int a[8]; for(int i = 0; i < 3; ++i) { //三种操作 memcpy(a, p.a, sizeof(a)); walk(i, a); code = KT(a); if(!vis[code]) { vis[code] = 1; path[code] = path[p.code] + dir[i]; q.push(node(a, code)); } } } } void deal(int *a) { swap(a[4], a[7]); swap(a[5], a[6]); } int main() { deal(); bfs(); int a[8], b[8], ha[8]; char s[20]; while(scanf("%s", s) == 1) { for(int i = 0; i < 8; ++i) { a[i] = s[i] - '0' - 1; } deal(a); for(int i = 0; i < 8; ++i) { ha[a[i]] = i; } scanf("%s", s); for(int i = 0; i < 8; ++i) { b[i] = s[i] - '0' - 1; } deal(b); for(int i = 0; i < 8; ++i) a[i] = ha[b[i]]; int code = KT(a); cout << path[code] << endl; //cout << "HELLO" <<endl; } return 0; }
如有不当之处欢迎指出!