这题我第一次用的bfs + ELFhash，直接TLE，又换成bfs + 康托还是TLE，5000ms都过不了！！我一直调试，还是TLE，我才发觉应该是方法的问题。
今天早上起床怒学了一波A*算法，因为IDA*我很熟悉，因此A*也学得很快，曼哈顿距离也很容易理解，看了好多人都用的A*过掉的。我一直在想A*算法无法保证得到最短路啊，怎么能AC？我擦，后来一读题目，题目没说要最短路径啊，只要任意一条路就可以了。我就呵呵了，愤怒写了一波A*过掉。
思路：
1. 根据逆序数可以判断是否有解，如果当前逆序数为奇数一定无解，是偶数则进行搜索。
2. 利用康拓判重。
3. 启发函数 ： F = G + H. A*算法的精髓， G表示从初始状态到达当前状态的花费，H表示当前状态到达目标状态的花费，H只能大概估计，估计可用曼哈顿距离。曼哈顿距离介绍
AC代码
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 4e5 + 5;
int vis[maxn]; //close表用于判重
int goal[] = {1,2,3,4,5,6,7,8,0};
int st[9];
typedef int state[9];
struct node{
int a[9];
int g, h; // 估价函数
int ha, pos;
node() {
}
node(int *b, int g, int h, int ha, int pos):g(g), h(h), ha(ha), pos(pos){
memcpy(a, b, sizeof(a));
}
bool operator < (const node &p) const {
return h > p.h || (p.h == h && g > p.g); // h小在前，g小在前
}
};
struct Node{
int pre;
char dir;
}Pre[maxn];
const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
const char dir[] = {'r','l','u','d'};
int fact[9];
void deal() { //1~8阶乘打表，方便编码
fact[0] = 1;
for(int i = 1; i < 9; ++i) fact[i] = fact[i - 1] * i;
}
int cut(int *a) {
int cnt = 0;
for(int i = 0; i < 9; ++i) {
if(a[i] == 0) continue;
for(int j = i + 1; j < 9; ++j) {
if(a[j] != 0 && a[i] < a[j]) ++cnt;
}
}
return cnt;
}
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 print(int u) {
if(Pre[u].pre == -1) return;
print(Pre[u].pre);
printf("%c", Pre[u].dir);
}
int get_h(int *a) { //根据曼哈顿距离得到的估价函数
int cnt = 0;
for(int i = 0; i < 9; ++i) {
if(!a[i]) continue;
int x = (a[i] - 1) / 3, y = (a[i] - 1) % 3; //终点的position
cnt += abs(i / 3 - x) + abs(i % 3 - y);
}
return cnt;
}
int Astar() {
priority_queue<node>q;
int des = KT(goal); //目标
memset(vis, 0, sizeof(vis));
int code = KT(st);
vis[code] = 1;
Pre[code].dir = 'x';
Pre[code].pre = -1;
int pos;
for(int i = 0; i < 9; ++i) if(!st[i]) pos = i;
int g = 0, h = get_h(st);
q.push(node(st, g, h, code, pos));
while(!q.empty()) {
node p = q.top();
q.pop();
code = p.ha, g = p.g, h = p.h, pos = p.pos;
if(code == des) { // 找到答案
//printf("%d\n", g);
print(des);
return 1;
}
state &a = p.a;
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 code1 = KT(a);
if(vis[code1]) {
swap(a[pos], a[pz]);
continue;
}
vis[code1] = 1;
Pre[code1].dir = dir[i];
Pre[code1].pre = code;
q.push(node(a, g + 1, get_h(a), code1, pz));
swap(a[pos], a[pz]);
}
}
return -1;
}
int main() {
deal();
char str[50];
while(fgets(str, sizeof(str), stdin) != NULL) {
int ind = 0;
for(int i = 0; str[i] != '\n'; ++i) {
if(str[i] == 'x') st[ind++] = 0;
else if(str[i] >= '0' && str[i] <= '9') st[ind++] = str[i] - '0';
}
// 根据逆序数提前判定是否有解
//for(int i = 0; i < 9; ++i) printf("%d ", st[i]);
if(cut(st) % 2 == 1) {
printf("unsolvable\n");
continue;
}
if( Astar() == -1) printf("unsolvable");
printf("\n");
}
return 0;
}
如有不当之处欢迎指出！