题意：
给你一个地图，有的地方能走，有的地方不能走，然后给你一条蛇，问你这条蛇的头部走到1，1的位置的最少步数，注意，和贪吃蛇不太一样，就是蛇咬到自己身体的那个地方，具体怎么不一样自己模拟下那个数据就明白了。
思路：
敲了挺长时间的，可能是刚过完年回来半个月没写代码手有点生了，一开始有个SB的想法就是我感觉只标记蛇的头部和尾部就行了，索然在敲之前已经动摇了，但是还是硬着头皮敲了一个代码，果断WA了，然后就是敲正确的方式（估计我的也不是标准的，以为我是5000MS g++过的，直接踩线过的节奏，里面自己平感觉优化了一些），我是mark[x][y][v],x,y是蛇头坐标，v是蛇身体的状态，状态压缩（4进制的（其实感觉三进制也行，然后在加个蛇的方向，没尝试去写，状态少点，没准会快点））思路就是首先从蛇头后的第一个开始相对于蛇头的位置，上下左右，然后是蛇头后第二个相对于第一个的位置，上下左右，这样就可以用
x y v三个int来表示条蛇的位置和状态了，我的跑了5000MS，其实我感觉还有一个地方可以优化，就是我判断的时候浪费了l（蛇长度）的时间，其实我们可以空间换时间，我觉得可以在每个结构体里面开个二维的map来标记当前的蛇的身体（为了判断撞到自己身体用的）更新这个O(1)的时间，至于蛇状态之间的转换，可以直接用取余的方法把最高位去掉，然后*4，然后再把第一位填上，这个操作的时间复杂度也是O(1)的，对于我的总时间复杂度的话T的话优化后是大约 T/L的，这个是理论值，具体的我也没去敲，我是这么想的，有兴趣的可以敲下试试，最好就是用三个方向，然后在空间换时间去优化，估计能快点。但是想刷排名还是用A*吧，虽然我现在不会。
#include<queue>
#include<stdio.h>
#include<string.h>
#define N 20 + 1
#define M 16384
using namespace std;
typedef struct
{
int x ,y;
}NODE;
typedef struct
{
int x ,y ,v ,t;
}P;
P tou ,xin;
NODE S[10];
int map[N][N] ,n ,m ,l;
int mark[N][N][M];
int dir[4][2] = {-1 ,0 ,1 ,0 ,0 ,-1 ,0 ,1};
int GetXinV()//得到xin.v并且判断是否撞到自己
{
int tmp = 4;
int x = tou.x ,y = tou.y;
for(int i = 2 ;i <= l ;i ++)
{
int now = tou.v % tmp / (tmp / 4);
if(i <= l - 1) xin.v += now * tmp;
x = x + dir[now][0];
y = y + dir[now][1];
if(x == xin.x && y == xin.y)
return 0;
tmp *= 4;
}
return 1;
}
bool ok(int x ,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m && !map[x][y];
}
int BFS()
{
memset(mark ,0 ,sizeof(mark));
mark[xin.x][xin.y][xin.v] = 1;
queue<P>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
//printf("%d %d %d**
" ,tou.x ,tou.y ,tou.v);
if(tou.x == 1 && tou.y == 1)
return tou.t;
for(int i = 0 ;i < 4 ;i ++)
{
xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.t = tou.t + 1;
xin.v = i ^ 1;
if(!ok(xin.x ,xin.y)) continue;
if(GetXinV())
{
if(!mark[xin.x][xin.y][xin.v])
{
mark[xin.x][xin.y][xin.v] = 1;
if(xin.x == 1 && xin.y == 1)
return xin.t;
q.push(xin);
}
}
}
}
return -1;
}
int main ()
{
int i ,x ,y ,cas = 1;
while(~scanf("%d %d %d" ,&n ,&m ,&l) && n + m + l)
{
for(i = 1 ;i <= l ;i ++)
scanf("%d %d" ,&S[i].x ,&S[i].y);
memset(map ,0 ,sizeof(map));
scanf("%d" ,&i);
while(i--)
{
scanf("%d %d" ,&x ,&y);
map[x][y] = 1;
}
xin.x = S[1].x ,xin.y = S[1].y;
xin.t = xin.v = 0;
int tmp = 1;
for(i = 2 ;i <= l ;i ++)
{
int now;
if(S[i].x - S[i-1].x == 1) now = 1;
else if(S[i].x - S[i-1].x == -1) now = 0;
else if(S[i].y - S[i-1].y == 1) now = 3;
else now = 2;
xin.v += now * tmp;
tmp *= 4;
}
printf("Case %d: %d
" ,cas ++ ,BFS());
}
}