题目：八数码
网址：http://poj.org/problem?id=1077
在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。
例如：
1 2 3
X 4 6
7 5 8
在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
输入格式
输入占一行，将3×3的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。如果答案不唯一，输出任意一种合法方案即可。
如果不存在解决方案，则输出”unsolvable”。
输入样例：
2 3 4 1 5 x 7 6 8
输出样例:
ullddrurdllurdruldr
很经典的一道广搜题目（A*）。核心就是如何保存状态。
- 方法一：使用map来记录操作以及set判重。
- 方法二：康托展开（早晚更新的）。
- 方法三：hash表判重，码量较大。
STL代码如下：
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define pii pair <int, int>
using namespace std;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int st, ed = 123456780;
set <int> vis;
map <int, int> d, f;
void decode(int state, int *p)
{
for(int i = 0; i < 9; ++ i)
{
p[8 - i] = state % 10;
state /= 10;
}
return;
}
int encode(int *p)
{
int t = 0;
for(int i = 0; i < 9; ++ i)
{
t = (t << 3) + (t << 1);
t += p[i];
}
return t;
}
int gh(int *p)
{
int cost = 0;
for(int i = 0; i < 9; ++ i)
cost += abs(i / 3 - (p[i] - 1) / 3) + abs(i % 3 - (p[i] - 1) % 3);
return cost;
}
void print(int state)
{
if(state == st) return;
int pre_state = f[state];
print(pre_state);
int i, p1[9] = {}, p2[9] = {}, t1 = -1, t2 = -1;
decode(state, p1), decode(pre_state, p2);
for(i = 0; i < 9; ++ i)
{
if(p1[i] == 0)
{
t1 = i;
break;
}
}
for(i = 0; i < 9; ++ i)
{
if(p2[i] == 0)
{
t2 = i;
break;
}
}
if(t1 < t2)
{
if(t1 - t2 == -1) putchar('l');
else putchar('u');
}
else
{
if(t2 - t1 == -1) putchar('r');
else putchar('d');
}
return;
}
bool valid(int x, int y)
{
if(x < 0 || x > 2 || y < 0 || y > 2) return false;
return true;
}
bool hash_table_judge(int state)
{
if(vis.count(state)) return false;
return true;
}
void hash_table_insert(int next_state, int state)
{
d[next_state] = d[state] + 1;
vis.insert(next_state);
f[next_state] = state;
return;
}
int bfs()
{
if(st == ed) return 0;
d.clear(), vis.clear(), f.clear();
queue <int> Q;
while(!Q.empty()) Q.pop();
int state, next_state, now, next, p[9], x, y;
memset(p, -1, sizeof(p));
hash_table_insert(st, 0);
d[st] = 0;
Q.push(st);
while(!Q.empty())
{
state = Q.front();
Q.pop();
decode(state, p);
for(int i = 0; i < 9; ++ i)
{
if(p[i] == 0)
{
now = i;
x = i / 3, y = i % 3;
break;
}
}
for(int i = 0; i < 4; ++ i)
{
if(!valid(x + dx[i], y + dy[i])) continue;
next = (x + dx[i]) * 3 + (y + dy[i]);
swap(p[now], p[next]);
next_state = encode(p);
swap(p[now], p[next]);
if(!hash_table_judge(next_state)) continue;
hash_table_insert(next_state, state);
if(next_state == ed)
{
printf("%d\n", d[state]);
print(state);
return 1;
}
Q.push(next_state);
}
}
return -1;
}
int main()
{
string line;
getline(cin, line);
for(int i = 0; i < line.size(); ++ i)
{
if(line[i] == 'x')
{
line[i] = '0';
break;
}
}
stringstream ss(line);
int tmp;
st = 0;
for(int i = 0; i < 9; ++ i)
{
ss >> tmp;
st = (st << 3) + (st << 1);
st += tmp;
}
if(bfs() == -1) puts("unsolvable");
return 0;
}
hash表代码如下：
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#define pii pair <int, int>
using namespace std;
const int maxn = 377777 + 5, mod = 377777;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
int st, ed = 123456780, head[maxn] = {}, next[maxn] = {}, table[maxn] = {}, tot = 0;
map <int, int> d, f;
void decode(int state, int *p)
{
for(int i = 0; i < 9; ++ i)
{
p[8 - i] = state % 10;
state /= 10;
}
return;
}
int encode(int *p)
{
int t = 0;
for(int i = 0; i < 9; ++ i)
{
t = (t << 3) + (t << 1);
t += p[i];
}
return t;
}
int hash_table_search(int state)
{
int val = state % mod;
for(int i = head[val]; i; i = next[i])
if(table[i] == state) return i;
return -1;
}
int gh(int *p)
{
int cost = 0;
for(int i = 0; i < 9; ++ i)
cost += abs(i / 3 - (p[i] - 1) / 3) + abs(i % 3 - (p[i] - 1) % 3);
return cost;
}
void print(int state)
{
if(state == st) return;
int pre_state = f[state];
print(pre_state);
int i, p1[9] = {}, p2[9] = {}, t1 = -1, t2 = -1;
decode(state, p1), decode(pre_state, p2);
for(i = 0; i < 9; ++ i)
{
if(p1[i] == 0)
{
t1 = i;
break;
}
}
for(i = 0; i < 9; ++ i)
{
if(p2[i] == 0)
{
t2 = i;
break;
}
}
if(t1 < t2)
{
if(t1 - t2 == -1) putchar('l');
else putchar('u');
}
else
{
if(t2 - t1 == -1) putchar('r');
else putchar('d');
}
return;
}
bool valid(int x, int y)
{
if(x < 0 || x > 2 || y < 0 || y > 2) return false;
return true;
}
bool hash_table_judge(int state)
{
int val = state % mod;
for(int i = head[val]; i; i = next[i])
if(table[i] == state) return false;
return true;
}
void hash_table_insert(int next_state, int state)
{
int val = next_state % mod;
table[++ tot] = next_state;
next[tot] = head[val];
head[val] = tot;
f[next_state] = state;
d[next_state] = d[state] + 1;
return;
}
int bfs()
{
if(st == ed) return 0;
d.clear(), f.clear();
queue <int> Q;
while(!Q.empty()) Q.pop();
int state, next_state, now, next, p[9], x, y;
memset(p, -1, sizeof(p));
hash_table_insert(st, 0);
d[st] = 0;
Q.push(st);
while(!Q.empty())
{
state = Q.front();
Q.pop();
decode(state, p);
for(int i = 0; i < 9; ++ i)
{
if(p[i] == 0)
{
now = i;
x = i / 3, y = i % 3;
break;
}
}
for(int i = 0; i < 4; ++ i)
{
if(!valid(x + dx[i], y + dy[i])) continue;
next = (x + dx[i]) * 3 + (y + dy[i]);
swap(p[now], p[next]);
next_state = encode(p);
swap(p[now], p[next]);
if(!hash_table_judge(next_state)) continue;
hash_table_insert(next_state, state);
if(next_state == ed)
{
print(state);
return d[state];
}
Q.push(next_state);
}
}
return -1;
}
int main()
{
string line;
getline(cin, line);
for(int i = 0; i < line.size(); ++ i)
{
if(line[i] == 'x')
{
line[i] = '0';
break;
}
}
stringstream ss(line);
int tmp;
st = 0;
for(int i = 0; i < 9; ++ i)
{
ss >> tmp;
st = (st << 3) + (st << 1);
st += tmp;
}
if(bfs() == -1) puts("unsolvable");
return 0;
}