这道题目最开始做的时候wa+TLE。后面知道需要状态压缩，最近A掉。并且练习一下各种搜索算法。
1. 逆向BFS+康拓展开。
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std; #define N 9
#define MAXNUM 362880 typedef struct {
char map[N];
int xpos;
string path;
} node_st; int fact[N] = {,,,,,,,,};
int direct[][] = {{-,},{,},{,-},{,}};
char rmove[] = {'d','u','r','l'};
char visit[MAXNUM];
string rpath[MAXNUM]; int cantor(node_st node) {
int i, j, cnt, val = ; for (i=; i<N; ++i) {
cnt = ;
for (j=i+; j<N; ++j) {
if (node.map[j] < node.map[i])
++cnt;
}
val += fact[N--i]*cnt;
} return val;
} void bfs() {
queue<node_st> que;
node_st node;
int i, x, y, t1, t2, can; for (i=; i<N; ++i)
node.map[i-] = '' + i;
node.map[N-] = 'x';
node.xpos = N-;
memset(visit, , sizeof(visit));
visit[] = ;
que.push(node); while ( !que.empty() ) {
node = que.front();
que.pop();
t1 = node.xpos / ;
t2 = node.xpos % ;
for (i=; i<; ++i) {
x = t1 + direct[i][];
y = t2 + direct[i][];
if (x< || x>= || y< || y>=)
continue;
node_st tmp(node);
tmp.xpos = x*+y;
tmp.map[node.xpos] = node.map[tmp.xpos];
tmp.map[tmp.xpos] = 'x';
can = cantor(tmp);
if ( !visit[can] ) {
visit[can] = ;
tmp.path += rmove[i];
rpath[can] = tmp.path;
que.push(tmp);
}
}
}
} int main() {
node_st node;
int i, can; bfs(); while (scanf("%c%*c", &node.map[]) != EOF) {
for (i=; i<N; ++i)
scanf("%c%*c", &node.map[i]);
can = cantor(node);
if ( visit[can] ) {
for (i=rpath[can].size()-; i>=; --i)
printf("%c", rpath[can][i]);
printf("\n");
} else {
printf("unsolvable\n");
}
} return ;
}
2. 双端BFS。注意逆序奇偶性相同才有解。
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std; #define N 9
#define MAXNUM 362880 typedef struct {
char map[N];
int xpos;
string path;
} node_st; int fact[N]={,,,,,,,,};
int direct[][] = {{-,},{,},{,-},{,}};
char move[] = {'u','d','l','r'};
char rmove[] = {'d','u','r','l'};
char visit[MAXNUM];
bool flag;
string paths[MAXNUM], fpath;
queue<node_st> que, rque; inline int cantor(node_st node) {
int i, j, cnt, val = ; for (i=; i<N; ++i) {
cnt = ;
for (j=i+; j<N; ++j)
if (node.map[j] < node.map[i])
++cnt;
val += fact[N--i]*cnt;
} return val;
} inline bool invNum(node_st node) {
int i, j, cnt = ; for (i=; i<N; ++i) {
if (node.map[i] == 'x')
continue;
for (j=i-; j>=; --j)
if (node.map[j]!='x' && node.map[j]>node.map[i])
++cnt;
} return cnt&;
} void bfs() {
int x, y, can;
node_st node = que.front();
que.pop(); for (int i=; i<; ++i) {
x = node.xpos/ + direct[i][];
y = node.xpos% + direct[i][];
if (x< || x>= || y< || y>=)
continue;
node_st p(node);
p.map[p.xpos] = node.map[x*+y];
p.xpos = x*+y;
p.map[p.xpos] = 'x';
can = cantor(p);
if (visit[can] == )
continue;
p.path += move[i];
if (visit[can] == -) {
flag = false;
reverse(paths[can].begin(), paths[can].end());
fpath = p.path + paths[can];
return ;
}
visit[can] = ;
paths[can] = p.path;
que.push(p);
}
} void rbfs() {
int x, y, can;
node_st node = rque.front();
rque.pop(); for (int i=; i<; ++i) {
x = node.xpos/ + direct[i][];
y = node.xpos% + direct[i][];
if (x< || x>= || y< || y>=)
continue;
node_st p(node);
p.map[p.xpos] = node.map[x*+y];
p.xpos = x*+y;
p.map[p.xpos] = 'x';
can = cantor(p);
if (visit[can] == -)
continue;
p.path += rmove[i];
if (visit[can] == ) {
flag = false;
reverse(p.path.begin(), p.path.end());
fpath = paths[can] + p.path;
}
visit[can] = -;
paths[can] = p.path;
rque.push(p);
}
} int main() {
node_st node, enode;
int i, n, can; for (i=; i<N; ++i)
enode.map[i-] = i + '';
enode.map[N-] = 'x';
enode.xpos = N-; while (scanf("%c%*c", &node.map[]) != EOF) {
for (i=; i<N; ++i) {
if (i)
scanf("%c%*c", &node.map[i]);
if (node.map[i] == 'x')
node.xpos = i;
}
if ( invNum(node) ) {
printf("unsolvable\n");
continue;
}
can = cantor(node);
if ( can == ) {
printf("\n");
continue;
}
while ( !que.empty() )
que.pop();
while ( !rque.empty() )
rque.pop();
memset(visit, , sizeof(visit));
flag = true;
rque.push(enode);
visit[] = -;
que.push(node);
visit[can] = ;
while (flag) {
n = que.size();
while (flag && n--)
bfs();
n = rque.size();
while (flag && n--)
rbfs();
}
cout <<fpath<<endl;
} return ;
}
3. A-star h函数为曼哈顿距离，必须用内联才不会TLE。
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std; #define N 9
#define MAXN 362880
//#define myabs(x) ((x)>0) ? (x):(-(x)) typedef struct node_st {
char map[N];
int xpos;
int s, p;
friend bool operator < (node_st a, node_st b) {
return a.p > b.p;
}
} node_st; char visit[MAXN];
int fact[N] = {,,,,,,,,};
int direct[][] = {{-,},{,},{,-},{,}};
char move[] = {'u', 'd', 'l', 'r'};
int pre[MAXN], bcan;
char op[MAXN];
node_st beg; inline int cantor(node_st node) {
int i, j, cnt, val = ; for (i=; i<N; ++i) {
cnt = ;
for (j=i+; j<N; ++j)
if (node.map[j] < node.map[i])
++cnt;
val += fact[N--i]*cnt;
} return val;
} inline myabs(int x) {
return (x>) ? x:-x;
} inline int h(node_st node) {
int tmp, val = ; for (int i=; i<N; ++i) {
if (node.map[i] == 'x') continue;
tmp = node.map[i] - '';
val += myabs(tmp/-i/) + myabs(tmp%-i%);
} return val;
} inline bool invNum(node_st node) {
int i, j, cnt = ; for (i=; i<N; ++i) {
if (node.map[i] == 'x') continue;
for (j=i-; j>=; --j)
if (node.map[j]!='x' && node.map[j]>node.map[i])
++cnt;
} return cnt&;
} void bfs() {
priority_queue<node_st> que;
node_st node;
int i, t1, t2, x, y, can, pcan; que.push(beg);
memset(visit, , sizeof(visit));
visit[bcan] = ; while ( !que.empty() ) {
node = que.top();
que.pop();
t1 = node.xpos / ;
t2 = node.xpos % ;
pcan = cantor(node);
for (i=; i<; ++i) {
x = t1 + direct[i][];
y = t2 + direct[i][];
if (x< || x>= || y< || y>=)
continue;
node_st p(node);
p.map[node.xpos] = p.map[x*+y];
p.xpos = x*+y;
p.map[p.xpos] = 'x';
can = cantor(p);
if (visit[can])
continue;
visit[can] = ;
++p.s;
p.p = p.s + h(p);
pre[can] = pcan;
op[can] = move[i];
if (can == )
return ;
que.push(p);
}
}
} int main() {
int i, k;
stack<char> st; while (scanf("%c%*c", &beg.map[]) != EOF) {
for (i=; i<N; ++i) {
if (i)
scanf("%c%*c", &beg.map[i]);
if (beg.map[i] == 'x')
beg.xpos = i;
}
beg.s = ;
beg.p = h(beg);
if ( invNum(beg) ) {
printf("unsolvable\n");
continue;
}
bcan = cantor(beg);
if (bcan == ) {
printf("\n");
continue;
}
bfs();
k = ;
while (k != bcan) {
st.push(op[k]);
k = pre[k];
} while ( !st.empty() ) {
printf("%c", st.top());
st.pop();
}
printf("\n");
}
return ;
}
4. IDA*，该算法其实是迭代dfs。H函数还是曼哈顿距离。
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std; #define N 9
#define MAXN 362880 typedef struct {
char map[N];
int xpos;
} node_st; int fact[N] = {,,,,,,,,};
int direct[][] = {{-,},{,},{,-},{,}};
char move[] = {'u', 'd', 'l', 'r'};
char visit[MAXN];
char op[MAXN];
int deep;
bool flag;
node_st beg; inline int cantor(node_st node) {
int i, j, cnt, val = ; for (i=; i<N; ++i) {
cnt = ;
for (j=i+; j<N; ++j)
if (node.map[j] < node.map[i])
++cnt;
val += fact[N--i]*cnt;
} return val;
} inline bool invNum(node_st node) {
int i, j, cnt = ; for (i=; i<N; ++i) {
if (node.map[i] == 'x') continue;
for (j=i-; j>=; --j)
if (node.map[j]!='x' && node.map[j]>node.map[i])
++cnt;
} return cnt&;
} inline int myabs(int x) {
return (x<) ? -x:x;
} inline int h(node_st node) {
int i, tmp, val = ; for (i=; i<N; ++i) {
if (node.map[i] == 'x') continue;
tmp = node.map[i] - '';
val += myabs(tmp/-i/) + myabs(tmp%-i%);
} return val;
} void dfs(int d) {
int i, t1, t2, x, y, can; t1 = h(beg);
if (t1 == ) {
flag = false;
return ;
}
if (t1+d > deep)
return ;
t1 = beg.xpos / ;
t2 = beg.xpos % ;
for (i=; i<; ++i) {
x = t1 + direct[i][];
y = t2 + direct[i][];
if (x< || x>= || y< || y>=)
continue;
node_st p(beg), org(beg);
p.map[p.xpos] = p.map[x*+y];
p.xpos = x*+y;
p.map[p.xpos] = 'x';
can = cantor(p);
if (visit[can]) continue;
visit[can] = ;
op[d] = move[i];
beg = p;
dfs(d+);
if ( !flag )
return ;
beg = org;
visit[can] = ;
}
} int main() {
int i; while (scanf("%c%*c", &beg.map[]) != EOF) {
for (i=; i<N; ++i) {
if (i)
scanf("%c%*c", &beg.map[i]);
if (beg.map[i] == 'x')
beg.xpos = i;
}
if ( invNum(beg) ) {
printf("unsolvable\n");
continue;
}
memset(visit, , sizeof(visit));
memset(op, , sizeof(op));
i = cantor(beg);
visit[i] = ;
deep = h(beg);
flag = true;
while (flag) {
++deep;
dfs();
//printf("%d\n", deep);
} i = ;
while ( op[i] )
printf("%c", op[i++]);
printf("\n");
} return ;
}