题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1043

  八数码问题,因为固定了位置所以以目标位置开始搜索,把所有情况(相当于一个排列)都记录下来,用康托展开来完成序列的记录问题开始BFS。打好表后按给出序列的康托数确定开始位置,逆向查找。

 #include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; typedef struct Node1 {
char s;
int pre;
Node1() { pre = -; }
}Node1;
typedef struct Node2 {
int status[];
int n, son;
}Node2; Node1 path[];
int dx[] = {, -, , };
int dy[] = {, , , -};
int fac[]; void init() {
fac[] = fac[] = ;
for(int i = ; i <= ; i++) {
fac[i] = fac[i-] * i;
}
} int ecantor(int* s, int n = ) {
int num = ;
for(int i = ; i < n; i++) {
int tmp = ;
for(int j = i + ; j < n; j++) {
if(s[j] < s[i]) {
tmp++;
}
}
num += fac[n--i] * tmp;
}
return num;
} void bfs() {
queue<Node2> q;
Node2 a, b;
int t = ;
for(int i = ; i < ; i++) {
a.status[i] = i + ;
}
a.n = ; a.son = ;
path[a.son].pre = ;
q.push(a);
while(!q.empty()) {
a = q.front(); q.pop();
for(int i = ; i < ; i++) {
b = a;
int xx = a.n % + dx[i];
int yy = a.n / + dy[i];
if(!(xx >= && xx < && yy >= && yy < )) continue;
b.n = yy * + xx;
swap(b.status[b.n], b.status[a.n]);
b.son = ecantor(b.status);
if(path[b.son].pre == -) {
path[b.son].pre = a.son;
if(i == ) path[b.son].s = 'l';
if(i == ) path[b.son].s = 'r';
if(i == ) path[b.son].s = 'u';
if(i == ) path[b.son].s = 'd';
q.push(b);
}
}
}
} int main() {
// freopen("in", "r", stdin);
init();
int s, ss[];
char ch[];
bfs();
while(gets(ch)) {
int cnt = ;
for(int i = ; ch[i]; i++) {
if(ch[i] == 'x') {
ss[cnt++] = ;
}
else if(ch[i] >= '' && ch[i] <= '') {
ss[cnt++] = ch[i] - '';
}
}
s = ecantor(ss);
if(path[s].pre == -) {
printf("unsolvable\n");
continue;
}
while(s != ) {
printf("%c", path[s].s);
s = path[s].pre;
}
printf("\n");
}
return ;
}
04-25 22:53