题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=361
BFS。。ZOJ的数据相对poj水了点，直接BFS。就可以过了、这题关键是判重，把蛇头坐标和蛇身相对坐标表示出来。。在获取蛇身的相对坐标时搞错了。导致错了N次。
计算蛇身时，要把蛇头去掉。也就是l-1，= =!
对于poj的数据，我用的a*过的。。稍微加了一下优化。。评估函数为当前步数加上蛇头到（1,1）的至少应该走的步数。 （单独） 蛇头到（1,1）的至少应走的步数的计算，也就是不计算蛇身的位置。那么直接BFS就可以了。
如果还加上蛇身。效率应该更快。但是我这样写简便一点。
下面是没优化的代码：
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn =21;
int n,m,l,find,ans,move;
bool map[maxn][maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool vis[maxn][maxn][1<<14];
bool check(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m; }
struct node{
int head[2],tail[2];
bool map[maxn][maxn];
int step,val;
}s_pos;
void bfs(){
memset(vis,false,sizeof(vis));
queue<node > q; q.push(s_pos);
vis[s_pos.head[0]][s_pos.head[1]][ s_pos.val] =true;
while(!q.empty()){
node now = q.front(); q.pop();
if(now.head[0]==1&&now.head[1]==1){
find=1; ans=now.step;
return ;
}
for(int i=0;i<4;i++){
node next = now; next.step+=1;
int x=now.head[0]+dx[i]; int y=now.head[1]+dy[i];
if(check(x,y)){
if(next.map[x][y]) continue;
next.head[0]=x; next.head[1]=y;
next.map[x][y]=true;
next.map[now.tail[0]][now.tail[1]]=false;
int t= next.val&3;
next.tail[0]=now.tail[0]+dx[t];
next.tail[1]=now.tail[1]+dy[t];
next.val=next.val>>2;
int sum=i<<move;
next.val+=sum;
if(!vis[x][y][next.val]){
vis[x][y][next.val]=true;
q.push(next);
}
}
}
}
}
int main(){
int t,x,y,ca=1;
int nx[10],ny[10];
while(scanf("%d%d%d",&n,&m,&l)!=EOF,(n+m+l)){
memset(s_pos.map,false,sizeof(s_pos.map));
memset(map,false,sizeof(map));
s_pos.val=0; move=((l<<1)-4);
for(int i=0;i<l;i++) {
scanf("%d%d",&x,&y);
nx[i]=x;ny[i]=y;
s_pos.map[x][y]=true;
if(i>0){
for(int j=0;j<4;j++){
if(x+dx[j]==nx[i-1]&&y+dy[j]==ny[i-1]){
s_pos.val=(s_pos.val<<2)+j;
break;
}
}
}
}
s_pos.head[0]=nx[0], s_pos.head[1]=ny[0];
s_pos.tail[0]=nx[l-1];s_pos.tail[1]=ny[l-1];
scanf("%d",&t); s_pos.step=0;
for(int i=0;i<t;i++){
scanf("%d%d",&x,&y);
map[x][y]=true;
s_pos.map[x][y]=true;
}
find=0; bfs();
printf("Case %d: ",ca++);
if(find){
printf("%d\n",ans);
}
else printf("-1\n");
}
return 0;
}
下面是优化的代码：
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn =21;
int n,m,l,fond,ans,move,ca;
bool map[maxn][maxn];
int cnt[maxn][maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
unsigned char vis[maxn][maxn][1<<14];
inline bool check(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m; }
struct node{
int head[2],tail[2];
bool map[maxn][maxn];
int step,val;
bool operator <(const node &a) const{
return cnt[a.head[0]][a.head[1]]+a.step<cnt[head[0]][head[1]]+step;
}
}s_pos;
void get_min(){
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cnt[i][j]=1000000;
cnt[1][1]=0;
queue<int > q;q.push(1); q.push(1);
while(!q.empty()){
int x=q.front(); q.pop();int y=q.front();q.pop();
for(int i=0;i<n;i++){
int nx=x+dx[i]; int ny=y+dy[i];
if(check(nx,ny)){
if(map[nx][ny]) continue ;
if(cnt[x][y]+1<cnt[nx][ny]){
cnt[nx][ny]=cnt[x][y]+1;
q.push(nx); q.push(ny);
}
}
}
}
}
void bfs(){
priority_queue<node > q; q.push(s_pos);
vis[s_pos.head[0]][s_pos.head[1]][ s_pos.val] =true;
while(!q.empty()){
node now = q.top(); q.pop();
if(now.head[0]==1&&now.head[1]==1){
fond=1; ans=now.step;
return ;
}
for(int i=0;i<4;i++){
node next = now; next.step+=1;
int x=now.head[0]+dx[i]; int y=now.head[1]+dy[i];
if(check(x,y)){
if(next.map[x][y]) continue;
next.head[0]=x; next.head[1]=y;
next.map[x][y]=true;
next.map[now.tail[0]][now.tail[1]]=false;
int t= next.val&3;
next.tail[0]=now.tail[0]+dx[t];
next.tail[1]=now.tail[1]+dy[t];
next.val=next.val>>2;
int sum=i<<move;
next.val+=sum;
if(vis[x][y][next.val]!=ca){
vis[x][y][next.val]=ca;
q.push(next);
}
}
}
}
}
int main(){
int t,x,y;
int nx[10],ny[10];
ca=1;
while(scanf("%d%d%d",&n,&m,&l)!=EOF,(n+m+l)){
memset(s_pos.map,false,sizeof(s_pos.map));
memset(map,false,sizeof(map));
s_pos.val=0; move=((l<<1)-4);
for(int i=0;i<l;i++) {
scanf("%d%d",&x,&y);
nx[i]=x;ny[i]=y;
s_pos.map[x][y]=true;
if(i>0){
for(int j=0;j<4;j++){
if(x+dx[j]==nx[i-1]&&y+dy[j]==ny[i-1]){
s_pos.val=(s_pos.val<<2)+j;
break;
}
}
}
}
s_pos.head[0]=nx[0], s_pos.head[1]=ny[0];
s_pos.tail[0]=nx[l-1];s_pos.tail[1]=ny[l-1];
scanf("%d",&t); s_pos.step=0;
for(int i=0;i<t;i++){
scanf("%d%d",&x,&y);
map[x][y]=true;
s_pos.map[x][y]=true;
}
fond=0; get_min(); bfs();
printf("Case %d: ",ca++);
if(fond){
printf("%d\n",ans);
}
else printf("-1\n");
}
return 0;
}