思路：
繼推箱子以后，又發(fā)現(xiàn)POJ上有這類題目，哈哈。
這次是給出一條貪食蛇當(dāng)前的狀態(tài)、墻的位置、食物的位置。求吃到食物需要走的最小的步數(shù)。
這類題目是相當(dāng)牛逼的！高手的速度可以做到很BT的。
在 status 上面就看到有 0ms 的！相當(dāng)震驚，如此龐大的數(shù)據(jù)量能做到 0ms，肯定是神牛！
后來搜了一下，還找到了那位神牛的博客，看了一下，發(fā)現(xiàn)看不大懂，杯具。。
哪一天有空，一定會(huì)再想一下這道題的。
一開始想了一個(gè)剪枝的方法，如果：
1. 蛇頭在可以穿越蛇的身體的情況下，到達(dá)食物所用的最小步數(shù)，
2. 蛇頭在不能穿越身體的情況下，到達(dá)食物所用的最小步數(shù)
這兩個(gè)值相等的話，就不用繼續(xù)擴(kuò)展當(dāng)前狀態(tài)了。
一開始覺得還挺牛逼，結(jié)果一提交 TLE了，無語了。POJ 的數(shù)據(jù)真不是蓋的，當(dāng)然主要問題還是哥的代碼太爛了。
后來改成現(xiàn)在這樣子了。跑了1秒+。。
表示蛇的狀態(tài)的時(shí)候，保存頭的位置、每段身體跟前一段偏移的方向。
不然沒法判重的。
#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;
}