题意：
迷宫里有一条贪食蛇，求它的蛇头到迷宫左上角最少要多少步。
分析：
关键是将蛇的状态压缩编码，然后bfs,超时就改A*,这题有类似最短路径的性质，A*发现节点重复后不需要更新直接舍弃即可。
代码：
//poj 1324
//sep9
#include <iostream>
#include <algorithm>
#include <queue>
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<l;++i){dir_num=3;dir_num&=s;s>>=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<l;++i)if(ss.x[i]==x&&ss.y[i]==y) return false;return true;
}int bfs()
{priority_queue<node> 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<l;++i)scanf("%d%d",&start.x[i],&start.y[i]);scanf("%d",&k);memset(g,0,sizeof(g)); for(int i=0;i<k;++i){int x,y;scanf("%d%d",&x,&y);g[x][y]=1;}printf("Case %d: %d\n",cases,bfs());} return 0;
}