codeforces 225D 搜索 哈希判重
链接：http://codeforces.com/problemset/problem/225/D
题意：给你一幅图，里面有一条贪吃蛇，问你这条蛇至少走几次能吃到苹果，或者永远都吃不到苹果。
这个题的关键是保存一条蛇的状态，一条蛇只要确定了头，然后其他的部分和上一部分都有一个方向上的相对关系，比如说长度为9的蛇，状态就可以表示为 蛇头 + 八个方向
即 （x*m+y 方向1 方向2 。。。 方向8）空间需求是15*15*4^8,这个状态可以用一个简单哈希来映射成一个整数保存，然后还要注意，蛇头走一步后，不能走到除尾巴外其他的自己身上的部位，因为尾巴会随着头的到来移走。
ps:写了个qiu_1A的函数，可惜还是RE了一次，囧
#include<cstdio>#include<cstring>#include<queue>using namespace std;int dir[4][2]={1,0,0,1,-1,0,0,-1};int n,m;char g[20][20];struct node {int x[10],y[10];int num;}s;int terx,tery;int len;queue<node> Q;int sx,sy;bool vis[20000000];int find_relative_dir(int a,int b,node s){for(int i=0;i<4;i++){ int x=s.x[b]+dir[i][0]; int y=s.y[b]+dir[i][1]; if(x==s.x[a] && y==s.y[a]) return i;}}int gethash(int sx,int sy,node s){int hash=sx*m+sy;for(int i=1;i<len;i++){hash=hash*4+find_relative_dir(i,i-1,s);}return hash;}void print(node s){for(int i=0;i<len;i++){printf("(%d %d)\n",s.x[i],s.y[i]);}}bool qiu_1A(){while(!Q.empty()){node f=Q.front();Q.pop();int x=f.x[0],y=f.y[0];for(int i=0;i<4;i++){ int tx=x+dir[i][0];int ty=y+dir[i][1];node tm;tm.x[0]=tx;tm.y[0]=ty;if(tx < 1 || ty < 1 || tx > n || ty > m || g[tx][ty]=='#') continue;bool flag=false;for(int j=1;j<len-1;j++) if(tx == f.x[j] && ty == f.y[j]) {flag=true;break;}if(flag) continue;for(int j=1;j<len;j++){tm.x[j]=f.x[j-1];tm.y[j]=f.y[j-1];}int hash=gethash(tx,ty,tm);if(!vis[hash]) {vis[hash] = true;tm.num = f.num+1;Q.push(tm);}if(tx == terx && ty == tery) return printf("%d\n",tm.num),true;}}return printf("-1\n"),true;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%s",g[i]+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(g[i][j]=='@'){terx=i;tery=j;}if(g[i][j] >= '1' && g[i][j] <='9'){if(g[i][j]=='1') sx=i,sy=j; s.x[g[i][j]-'1']=i;s.y[g[i][j]-'1']=j;len++;g[i][j]='.';}}} int hash=gethash(sx,sy,s);vis[hash]=true;s.num=0;Q.push(s);qiu_1A();return 0;}