题目：八数码难题
思路：bfs+hash判重。
注意：
1、hash的链表不能写错。
2、由于用的是一位数组，所以移动时要判断左右边界。比如当前的空位在5处，就不能向右移+1。
0 1 2
3 4 5
6 7 8
代码：
#include<iostream>
#include<cstdio>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define n 8
#define max_state 362880
#define Mod 1000003int head[Mod+5],nxt[Mod+5],val[Mod+5],num=0;struct State {int a[n+3];int o;int step;int id;void make_id() {id=0;for(int i=0; i<=n; i++) {id=id*10+a[i];}}bool find() {int x=id%Mod;int u=head[x];while(~u) {if(val[u]==id) return true;u=nxt[u];}return false;}void add() {int x=id%Mod;nxt[++num]=head[x];head[x]=num;val[num]=id;}bool judge() {if(id==123804765) return true;return false;}};bool Agree(int x,int mv){if(x+mv<0||x+mv>n) return false;if(mv==1&&(x==2||x==5||x==8)) return false;if(mv==-1&&(x==0||x==3||x==6)) return false;return true;
}const int m[5]= {1,-1,3,-3};
State que[max_state+5];
int bfs(State in) {int h=0,t=0;que[0]=in;que[0].make_id();if(que[0].judge()) return 0;que[0].add();while(h<=t) {State u=que[h];h++;for(int i=0; i<4; i++) {State x=u;if(Agree(x.o,m[i])) {swap(x.a[x.o],x.a[x.o+m[i]]);x.o+=m[i];x.step++;x.make_id();if(!x.find()) {x.add();que[++t]=x;}if(x.judge()) return x.step;}}}return -1;
}int main() {memset(head,-1,sizeof(head));memset(nxt,-1,sizeof(nxt));State x;for(int i=0; i<=n; i++) {char y=getchar();x.a[i]=y-'0';if(y=='0') {x.o=i;}}x.step=0;printf("%d",bfs(x));return 0;
}