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;
}

如有不当之处欢迎指出！