题目我就不粘贴了。。。
题意：给出地图，最大8*8，出口用'E'表示，空地用'.'表示，数字表示此处有多少个箱子，主人公的起点应该是在有箱子的地方，他可以朝四个方向移动，但是只有两种方式
一种是他移动到的位置也是有箱子的地方，另一种是空地，此时他可以把他所处位置的箱子全部推倒，朝那个方向铺成一条线，相当于每个地方一个箱子，但是所铺的位置原来
必须是 '.'，否则是不能移动。问主人公最少需要多少步才能到达出口。不能达到输出Impossible.
解析：这题难在保存状态，而不在搜索的过程，最多有64个格子，相当于64个数，那么我们可以考虑用哈希将这么多数哈希成一个值，如何哈希呢？我是给每个数乘上一个系数，
比如第一个数乘上1，第二个数乘上1+131，第3个数乘上1+131+131，依此下去，然后模上一个数，用链表保存哈希值和对应的结构体下标，因为可能会出现两种不同的
状态哈希成同一个值，所以保存结构体下标是为了比较整个状态（这种需要整体比较的情况很少），其实整个搜索的状态并不是很多，用用哈希，细点心基本就可以过了。
代码
#include<cstdio> #include<cstring> #include<string> #include<iostream> #include<sstream> #include<algorithm> #include<utility> #include<vector> #include<set> #include<map> #include<queue> #include<cmath> #include<iterator> #include<stack> using namespace std; const int INF=1e9+7; const double eps=1e-7; const int mod=300007; const int maxn=200005; int N,bex,bey; int dx[]={-1,0,1,0},dy[]={0,-1,0,1}; bool in(int x,int y){ return x>=0&&x<N&&y>=0&&y<N; } structnode { char S[8][8]; //结构体保存整个图和人的坐标 int x,y; }nod[maxn]; structHash { int v,nid,next; //保存哈希值，结构体下标，以及next指针 }ha[mod+maxn]; int f,r,hash_id; //队首队尾指针 int GetHash(char S[][8]) { int ret=0,k=1; for(int i=0;i<N;i++) for(int j=0;j<N;j++) //得到哈希值 { if(S[i][j]>='1'&&S[i][j]<='9') ret+=(S[i][j]-'0')*k; else ret+=11*k; k+=131; } return ret; } bool Same(int a,int b) //整个状态比较 { if(nod[a].x!=nod[b].x) return false; if(nod[a].y!=nod[b].y) return false; for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(nod[a].S[i][j]!=nod[b].S[i][j]) return false; return true; } bool Insert_Hash(int v,int nid) { int a=v%mod; int p=ha[a].next; while(p!=-1) { if(ha[p].v==v&&Same(ha[p].nid,nid)) return false; //出现相同的状态 p=ha[p].next; } p=++hash_id; //增加节点 ha[p].v=v; ha[p].nid=nid; ha[p].next=ha[a].next; ha[a].next=p; //前插法 return true; } bool check(node& t,int x,int y,int k) //检查能都铺 { int step=t.S[x][y]-'0'; if(step==1) return false; t.S[x][y]='.'; while(step--) { x+=dx[k]; y+=dy[k]; if(!in(x,y)||t.S[x][y]!='.') return false; //越界不行，不是'.'也不行 t.S[x][y]='1'; } return true; } void Print(node& t) { printf("%d %d ",t.x,t.y); for(int i=0;i<N;i++) printf("%s ",t.S[i]); puts("========="); } bool AddNode(node& t,int k) { int x=t.x,y=t.y; int nx=x+dx[k],ny=y+dy[k]; if(!in(nx,ny)) return false; if(t.S[nx][ny]=='E') return true; //到达出口 node& tt=nod[r]; tt=t; tt.x=nx; tt.y=ny; if(t.S[nx][ny]=='.') { if(!check(tt,x,y,k)) return false; } int a=GetHash(tt.S); if(Insert_Hash(a,r)) r++; //添加到队尾 //Print(tt); return false; } bool bfs() { int en=r; while(f<en) { node& t=nod[f++]; for(int i=0;i<4;i++) if(AddNode(t,i)) return true; } return false; } int solve() { if(nod[0].S[bex][bey]=='E') return 0; if(nod[0].S[bex][bey]=='.') return -1; for(int i=0;i<mod;i++) ha[i].next=-1; hash_id=mod-1; f=0,r=1; int step=0; while(f<r) { step++; if(bfs()) return step; } return -1; } int main() { while(scanf("%d%d%d",&N,&bex,&bey)!=EOF) { if(!N&&!bex&&!bey) break; nod[0].x=--bex; nod[0].y=--bey; for(int i=0;i<N;i++) scanf("%s",nod[0].S[i]); int ans=solve(); if(ans==-1) printf("Impossible. "); else printf("%d ",ans); } return 0; }