HDU - 3567 IDA* + 曼哈顿距离 + 康托 [kuangbin带你飞]专题二

     这题难度颇大啊，TLE一天了，测试数据组数太多了。双向广度优先搜索不能得到字典序最小的，一直WA。

     思路：利用IDA*算法，当前状态到达目标状态的可能最小步数就是曼哈顿距离，用于搜索中的剪枝。下次搜索的限制不能直接加1，会超时，应该从当前状态到目标状态最小限制开始搜索。

     AC代码

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>using namespace std;const int maxn = 4e5 + 5;int vis[maxn];int st[9], goal[9];const int dx[] = {1,0,0,-1};const int dy[] = {0,-1,1,0};const char dir[] = {'d','l','r','u'};int fact[9], loc[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;} void get_pos() {	for(int i = 0; i < 9; ++i) {		loc[goal[i]] = i;	}}int get_h(int *a) { //曼哈顿距离 	int cnt = 0;	for(int i = 0; i < 9; ++i) {		if(a[i] == 0 || i == loc[a[i]]) continue;		int x = i / 3, y = i % 3;		int n = loc[a[i]];		int px = n / 3, py = n % 3;		cnt += abs(x - px) + abs(y - py);	}	return cnt;}char ans[50];int a[9];// step + h <= maxd int maxd, nextd;int dfs(int step, int pos) {	int h = get_h(a); // cut	//PRintf("h = %d/n", h);	if(h == 0) {		printf("%d/n", step);		ans[step] = '/0';		printf("%s", ans);		return 1;	}	if(step + h > maxd) {		nextd = min(nextd, step + h);		return 0;	}	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[pos], a[pz]);		int code = KT(a);		if(vis[code]) {			swap(a[pos], a[pz]);			continue;		}		vis[code] = 1;		ans[step] = dir[i];		if(dfs(step + 1, pz)) return 1;		vis[code] = 0;		swap(a[pos], a[pz]);	}	return 0; } int main() {	deal(); 	char str[50];	int T, kase = 1;	scanf("%d", &T);	while(T--) {		int pos;		scanf("%s", str);		for(int i = 0; i < 9; ++i) {			if(str[i] == 'X') {				pos = i;				st[i] = 0;			}			else st[i] = str[i] - '0';		}						scanf("%s", str);		for(int i = 0; i < 9; ++i) {			if(str[i] == 'X') goal[i] = 0;			else goal[i] = str[i] - '0';		}		get_pos();				printf("Case %d: ", kase++);				int code = KT(st);		vis[code] = 1;		for(maxd = get_h(st);;) {			nextd = 1 << 30; 			memcpy(a, st, sizeof(a));			memset(vis, 0, sizeof(vis));			if(dfs(0, pos)) break;			maxd = nextd;		}		printf("/n");	}	return 0;}如有不当之处欢迎指出！