题意：八数码问题，对于给定的初始态，求出到达目标态的路径。
题目链接：http://poj.org/problem?id=1077
——>>上ACM课的，老师讲的例题，看老师的代码看不明白；寒假看白书，轻松AC，今天重刷一次，竟将目标状态写多了一个9，debug了好久。
这也是我所做的第一道哈希题；对于一个八数码图，对应着一个状态，那么总共会有9！个状态，近40万个， 可以将这些状态对应哈希值。那么，可以从一个初始状态开始搜，上、下、左、右地走，每走一次就判断是否已为目标态：
是的话，返回；
不是的话，记录这个状态已走过，下次再有转移到此状态的就不继续做处理了（现已处理）；
注意：结点查找表存的是队列的编号而不是状态。
#include <iostream>
#include <cstring>using namespace std;const int maxn = 1000003;
typedef int State[9];
State st[maxn];
int goal[] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
int head[maxn], nxt[maxn], fa[maxn];
char dir[maxn];int Hash(State s) //哈希函数
{int ret = 0, i;for(i = 0; i < 9; i++) ret = ret * 10 + s[i];return ret % maxn;
}bool try_to_insert(int rear) //插入哈希表
{int h = Hash(st[rear]);for(int e = head[h]; e != -1; e = nxt[e]){if(memcmp(st[e], st[rear], sizeof(st[e])) == 0) return 0;}nxt[rear] = head[h];head[h] = rear;return 1;
}int bfs() //遍历
{int frt = 1, rear = 2, i, z;while(frt < rear){State& s = st[frt];if(memcmp(s, goal, sizeof(s)) == 0) return frt;for(z = 0; s[z] != 0; z++);int x = z / 3;int y = z % 3;for(i = 0; i < 4; i++){int newx = x + dx[i];int newy = y + dy[i];int newz = 3 * newx + newy;if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3){State& news = st[rear];memcpy(news, s, sizeof(s));news[z] = s[newz];news[newz] = 0;if(try_to_insert(rear)){fa[rear] = frt;switch(i){case 0: dir[rear] = 'u'; break;case 1: dir[rear] = 'd'; break;case 2: dir[rear] = 'l'; break;case 3: dir[rear] = 'r'; break;default: break;}rear++;}}}frt++;}return 0;
}void print(int i) //输出
{if(fa[i] == -1) return;print(fa[i]);cout<<dir[i];
}int main()
{char c[10];int i, ret;while(cin>>c[0]>>c[1]>>c[2]>>c[3]>>c[4]>>c[5]>>c[6]>>c[7]>>c[8]){for(i = 0; i < 9; i++) st[1][i] = c[i] == 'x' ? 0 : (int)(c[i]-'0');memset(head, -1, sizeof(head));fa[1] = -1;ret = bfs();if(ret){print(ret);}else cout<<"unsolvable";cout<<endl;}return 0;
}