题意：

迷宫里有一条贪食蛇，求它的蛇头到迷宫左上角最少要多少步。

分析：

关键是将蛇的状态压缩编码，然后bfs,超时就改A*,这题有类似最短路径的性质，A*发现节点重复后不需要更新直接舍弃即可。

代码：

?

//poj 1324
//sep9
#include 
  
   
#include 
   
     #include 
    
      using namespace std; struct state { int x[10],y[10]; }; struct node { int x,y,s,k,f; bool operator <(const node &a) const{ return f>a.f; } }; int n,m,l,k,cases; int vis[22][22][1<<15]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int g[32][32]; state start; int encode(state s,int l) { int st=0; for(int i=l-1;i>0;--i){ int x,y,now; x=s.x[i]-s.x[i-1]; y=s.y[i]-s.y[i-1]; if(x==0&&y==1) now=2; else if(x==0&&y==-1) now=3; else if(x==1&&y==0) now=0; else if(x==-1&&y==0) now=1; st<<=2; st|=now; } return st; } state decode(int x,int y,int s,int l) { int dir_num; state p; p.x[0]=x,p.y[0]=y; for(int i=1;i
     
      >=2; p.x[i]=p.x[i-1]+dir[dir_num][0]; p.y[i]=p.y[i-1]+dir[dir_num][1]; } return p; } node moves(node s,int d,int l) { int now,x,y; s.x+=dir[d][0]; s.y+=dir[d][1]; x=-dir[d][0],y=-dir[d][1]; if(x==0&&y==1) now=2; else if(x==0&&y==-1) now=3; else if(x==1&&y==0) now=0; else if(x==-1&&y==0) now=1; s.s<<=2; s.s|=now; s.s&=((1<<((l-1)*2))-1); return s; } bool judge(int x,int y,int s,node pre) { if(x<1||x>n||y<1||y>m) return false; if(vis[x][y][s]==cases) return false; if(g[x][y]==1) return false; state ss=decode(pre.x,pre.y,pre.s,l); for(int i=0;i
      
        q; node a,tp; a.x=start.x[0],a.y=start.y[0]; a.s=encode(start,l); a.k=0; a.f=a.x+a.y; q.push(a); vis[a.x][a.y][a.s]=cases; while(!q.empty()){ a=q.top();q.pop(); state tmp=decode(a.x,a.y,a.s,l); if(a.x==1&&a.y==1) return a.k; for(int i=0;i<4;++i){ tp=moves(a,i,l); tp.k=a.k+1; if(!judge(tp.x,tp.y,tp.s,a)) continue; vis[tp.x][tp.y][tp.s]=cases; tp.f=tp.k+tp.x+tp.y; q.push(tp); } } return -1; } int main() { cases=0; while(scanf("%d%d%d",&n,&m,&l)==3&&(n+m+l)){ ++cases; for(int i=0;i
       
        
?
        
?