HDU - 1430 魔板 (bfs预处理 + 康托)

       对于该题可以直接预处理初始状态[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;}如有不当之处欢迎指出！