HDU - 3567 Eight II (bfs预处理 + 康托) [kuangbin带你飞]专题二

      类似HDU1430，不过本题需要枚举X的九个位置，分别保存状态，因为要保证最少步数。要保证字典序最小的话，在扩展节点时，方向顺序为：down, left, right, up.

     我用c++提交1500ms， G++提交858ms.

   AC代码

#include<cstdio>#include<cstring>#include<queue>#include<string>#include<iostream>#include<algorithm>using namespace std;typedef int state[9];const int maxn = 4e5 + 5;int vis[9][maxn];const int dx[] = {1,0,0,-1};const int dy[] = {0,-1,1,0};const char dir[] = {'d','l','r','u'};int fact[9];void deal() {  //1~8阶乘打表，方便编码 	fact[0] = 1;	for(int i = 1; i < 9; ++i) fact[i] = fact[i - 1] * i;}int KT(int *a) {	int code = 0;	for(int i = 0; i < 9; ++i) {		int cnt = 0;		for(int j = i + 1; j < 9; ++j) if(a[j] < a[i]) cnt++;		code += fact[8 - i] * cnt;	}	return code;} int find_pos(int *a) {	for(int i = 0; i < 9; ++i) {		if(a[i] == 0) return i;	}}struct node{	int a[9];	int code, step;	int pos;	node() {	}	node(int *b, int code, int step ,int pos):code(code), step(step), pos(pos) {		memcpy(a, b, sizeof(a));	}};struct Dirction {	char dir;	int step;	int PRe;	Dirction() {	}	Dirction(char dir, int step, int pre):dir(dir), step(step), pre(pre){	}}d[9][maxn];int st[9];void bfs(int c) {	queue<node>q;	int code = KT(st);	vis[c][code] = 1;	d[c][code] = Dirction('x', 0, -1);	int pp = find_pos(st);	q.push(node(st, code, 0, pp));	while(!q.empty()) {		node p = q.front();		q.pop();		state &a = p.a;		int pos = p.pos;		int x = pos / 3, y = pos % 3;		for(int i = 0; i < 4; ++i) {			int px = x + dx[i], py = y + dy[i];			if(px < 0 || py < 0 || px >= 3 || py >= 3) continue;			int pz = px * 3 + py;			swap(a[pz], a[pos]);			code = KT(a);			if(vis[c][code]) {				swap(a[pz], a[pos]);				continue;			}			vis[c][code] = 1;			d[c][code] = Dirction(dir[i], p.step + 1, p.code);			q.push(node(a, code, p.step + 1, pz));			swap(a[pz], a[pos]);		}	}}int op[][9] = {	0, 1, 2, 3, 4, 5, 6, 7, 8,	1, 0, 2, 3, 4, 5, 6, 7, 8,	1, 2, 0, 3, 4, 5, 6, 7, 8,	1, 2, 3, 0, 4, 5, 6, 7, 8,	1, 2, 3, 4, 0, 5, 6, 7, 8,	1, 2, 3, 4, 5, 0, 6, 7, 8,	1, 2, 3, 4, 5, 6, 0, 7, 8,	1, 2, 3, 4, 5, 6, 7, 0, 8,	1, 2, 3, 4, 5, 6, 7, 8, 0};void print(int code, int c) {	if(d[c][code].pre == -1) return;	print(d[c][code].pre, c);	printf("%c", d[c][code].dir);}int main() {	memset(vis, 0, sizeof(vis));	deal();	for(int i = 0; i < 9; ++i) {		memcpy(st, op[i], sizeof(st));		bfs(i);	}	int a[9], b[9];	int T, kase = 1, ha[9];	char s[20]; 	scanf("%d", &T);	while(T--) {		int pos;		scanf("%s", s);		for(int i = 0; i < 9; ++i) {			if(s[i] == 'X') {				pos = i;				a[i] = 0;			}			else a[i] = s[i] - '0';		}		for(int i = 0; i < 9; ++i) {			ha[a[i]] = op[pos][i];		}		scanf("%s", s);		for(int i = 0; i < 9; ++i) {			if(s[i] == 'X') b[i] = 0;			else b[i] = s[i] - '0';			a[i] = ha[b[i]];		}		int code = KT(a);		printf("Case %d: %d/n", kase++, d[pos][code].step);		print(code, pos);		printf("/n");	}		return 0;}如有不当之处欢迎指出！