思路：
继推箱子以后，又发现POJ上有这类题目，哈哈。
这次是给出一条贪食蛇当前的状态、墙的位置、食物的位置。求吃到食物需要走的最小的步数。
这类题目是相当牛逼的！高手的速度可以做到很BT的。
在 status 上面就看到有 0ms 的！相当震惊，如此庞大的数据量能做到 0ms，肯定是神牛！
后来搜了一下，还找到了那位神牛的博客，看了一下，发现看不大懂，杯具。。
哪一天有空，一定会再想一下这道题的。
一开始想了一个剪枝的方法，如果：
1. 蛇头在可以穿越蛇的身体的情况下，到达食物所用的最小步数，
2. 蛇头在不能穿越身体的情况下，到达食物所用的最小步数
这两个值相等的话，就不用继续扩展当前状态了。
一开始觉得还挺牛逼，结果一提交 TLE了，无语了。POJ 的数据真不是盖的，当然主要问题还是哥的代码太烂了。
后来改成现在这样子了。跑了1秒+。。
表示蛇的状态的时候，保存头的位置、每段身体跟前一段偏移的方向。
不然没法判重的。
#include <stdio.h>
#include <string.h>
#define QUEUE_SIZE (1 << 16)
struct node 
{
char y, x;
unsigned short s;
int step;
};
int N, M, L;
int hash[24][24][1 << 14], tm;
struct node queue[QUEUE_SIZE];
int head, tail;
char map[24][24];
unsigned short mask;
inline struct node input()
{
struct node t;
int y, x, i, nx, ny;
scanf("%d%d", &y, &x);
t.y = y;
t.x = x;
t.s = 0;
for (i = 0; i < L - 1; i++) {
scanf("%d%d", &ny, &nx);
if (nx == x)
t.s |= (ny < y ? 0 : 1) << (i * 2);
else
t.s |= (nx < x ? 2 : 3) << (i * 2);
y = ny;
x = nx;
}
t.step = 0;
return t;
}
inline void push(struct node t)
{
if (hash[t.y][t.x][t.s] == tm)
return ;
hash[t.y][t.x][t.s] = tm;
queue[tail++] = t;
tail &= QUEUE_SIZE - 1;
}
inline void move(struct node t, int dir)
{
int i, y, x;
y = t.y;
x = t.x;
switch (dir) {
case 0: t.y--; dir = 1; break;
case 1: t.y++; dir = 0; break;
case 2: t.x--; dir = 3; break;
case 3: t.x++; dir = 2; break;
}
if (t.y < 1 || t.y > N || t.x < 1 || t.x > M || map[t.y][t.x] == '@')
return ;
for (i = 0; i < L - 1; i++) {
switch ((t.s >> (i * 2)) & 3) {
case 0: y--; break;
case 1: y++; break;
case 2: x--; break;
case 3: x++; break;
}
if (t.y == y && t.x == x)
break;
}
if (i < L - 1)
return ;
t.s <<= 2;
t.s &= mask;
t.s |= dir;
t.step++;
push(t);
}
inline int bfs(struct node t)
{
head = tail = 0;
tm++;
push(t);
while (head != tail) {
t = queue[head++];
head &= QUEUE_SIZE - 1;
if (t.x == 1 && t.y == 1)
break;
move(t, 0);
move(t, 1);
move(t, 2);
move(t, 3);
}
return (t.x == 1 && t.y == 1) ? t.step : -1;
}
int main()
{
int y, x, c, k;
struct node t;
freopen("e:\\test\\in.txt", "r", stdin);
for (c = 1; scanf("%d%d", &N, &M), N; c++) {
memset(map, '.', sizeof(map));
scanf("%d", &L);
mask = (1 << ((L - 1) * 2)) - 1;
t = input();
scanf("%d", &k);
while (k--) {
scanf("%d%d", &y, &x);
map[y][x] = '@';
}
printf("Case %d: %d\n", c, bfs(t));
}
return 0;
}