题意：从无序到有序移动的方案，即最后成1 2 3 4 5 6 7 8 0
分析：八数码经典问题。POJ是一次，HDOJ是多次。因为康托展开还不会，也写不了什么，HDOJ需要从最后的状态逆向搜索，这样才不会超时。判重康托展开，哈希也可。
POJ
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include <cstring>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>
using namespace std; const int N = 362880 + 5;
const int MOD = 1e6 + 7;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
char dir[4] = {'u', 'd', 'l', 'r'};
struct Point {
int s, d;
string str;
Point () {}
Point (int s, int d, string str) : s (s), d (d), str (str) {}
};
struct Hash_table {
struct Edge {
int v, nex;
}edge[MOD];
int head[MOD], e;
void init(void) {
memset (head, -1, sizeof (head));
e = 0;
}
bool insert(int x) {
int u = (x % MOD + MOD) % MOD;
for (int i=head[u]; ~i; i=edge[i].nex) {
if (edge[i].v == x) return false;
}
edge[e].v = x; edge[e].nex = head[u];
head[u] = e++;
return true;
}
}ha;
int vis[N], fact[9]; void decode(int x, int *b) {
for (int i=8; i>=0; --i) {
b[i] = x % 10;
x /= 10;
}
} int encode(int *b) {
int ret = 0;
for (int i=0; i<9; ++i) {
ret = ret * 10 + b[i];
}
return ret;
} int find_0(int *b) {
for (int i=0; i<9; ++i) {
if (b[i] == 0) return i;
}
return -1;
} bool check(int x, int y) {
if (x < 0 || x >= 3 || y < 0 || y >= 3) return false;
else return true;
} void print(int *b) {
for (int i=0; i<9; ++i) {
printf ("%d ", b[i]);
if (i == 2 || i == 5 || i == 8) puts ("");
}
} void init(void) {
fact[0] = 1;
for (int i=1; i<9; ++i) fact[i] = fact[i-1] * i;
memset (vis, false, sizeof (vis));
} bool can_insert(int *b) {
int code = 0;
for (int i=0; i<9; ++i) {
int cnt = 0;
for (int j=i+1; j<9; ++j) if (b[j] < b[i]) cnt++;
code += fact[8-i] * cnt;
}
if (vis[code]) return false;
else {
vis[code] = true;
return true;
}
} void BFS(int *a) {
init ();
int ans[9] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
int s = encode (a);
queue<Point> que; que.push (Point (s, 0, ""));
while (!que.empty ()) {
Point u = que.front (); que.pop ();
int b[9];
decode (u.s, b);
if (memcmp (ans, b, sizeof (b)) == 0) {
int len = u.str.length ();
for (int i=0; i<len; ++i) {
printf ("%c", u.str[i]);
}
puts ("");
return ;
}
int p = find_0 (b);
int x = p / 3, y = p % 3;
for (int i=0; i<4; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (!check (tx, ty)) continue;
int p2 = tx * 3 + ty;
int t[9];
memcpy (t, b, sizeof (b));
t[p] = t[p2]; t[p2] = 0;
int v = encode (t);
//if (!ha.insert (v)) continue;
if (!can_insert (t)) continue;
que.push (Point (v, u.d + 1, u.str + dir[i]));
}
}
puts ("unsolvable");
} int main(void) {
char c[9];
int a[9];
while (scanf ("%c %c %c %c %c %c %c %c %c", &c[0], &c[1], &c[2], &c[3], &c[4], &c[5], &c[6], &c[7], &c[8]) == 9) {
for (int i=0; i<9; ++i) {
if (c[i] >= '1' && c[i] <= '9') {
a[i] = c[i] - '0';
}
else a[i] = 0;
}
BFS (a);
} return 0;
}
HDOJ
#include <bits/stdc++.h>
using namespace std; const int N = 362880 + 5;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
char dir[4] = {'d', 'u', 'r', 'l'};
struct Point {
int s;
int b[9];
};
struct Ans {
char dir;
int fa;
}ans[N];
int fact[9]; int find_0(int *b) {
for (int i=0; i<9; ++i) {
if (b[i] == 9) return i;
}
return -1;
} bool check(int x, int y) {
if (x < 0 || x >= 3 || y < 0 || y >= 3) return false;
else return true;
} void init(void) {
fact[0] = 1;
for (int i=1; i<9; ++i) fact[i] = fact[i-1] * i;
for (int i=0; i<N; ++i) ans[i].fa = -1;
} int Cantor(int *b) {
int code = 0;
for (int i=0; i<9; ++i) {
int cnt = 0;
for (int j=i+1; j<9; ++j) if (b[j] < b[i]) cnt++;
code += fact[8-i] * cnt;
}
return code;
} void BFS() {
init ();
Point sta;
for (int i=0; i<9; ++i) {
sta.b[i] = i + 1;
}
sta.s = 0; ans[sta.s].fa = 0;
queue<Point> que; que.push (sta);
while (!que.empty ()) {
Point u = que.front (); que.pop ();
int p = find_0 (u.b);
int x = p / 3, y = p % 3;
for (int i=0; i<4; ++i) {
Point v = u;
int tx = x + dx[i], ty = y + dy[i];
if (!check (tx, ty)) continue;
int p2 = tx * 3 + ty;
swap (v.b[p], v.b[p2]);
v.s = Cantor (v.b);
if (ans[v.s].fa != -1) continue;
ans[v.s].dir = dir[i];
ans[v.s].fa = u.s;
que.push (v);
}
}
} int main(void) {
BFS ();
char c[55];
int a[9];
while (gets (c)) {
int j = 0;
for (int i=0; c[i]; ++i) {
if (c[i] >= '0' && c[i] <= '8') {
a[j++] = c[i] - '0';
}
else if (c[i] == 'x') a[j++] = 9;
}
int s = Cantor (a);
if (ans[s].fa == -1) puts ("unsolvable");
else {
while (s != 0) {
printf ("%c", ans[s].dir);
s = ans[s].fa;
}
puts ("");
}
} return 0;
}