题意：

简单贪吃蛇问题，问最少经过多少步，贪吃蛇可以从点（1,1）出去。

思路：

1. 本题的状态设计，是一个难点所在：当头结点固定的时候，由于尾巴的长度最多不超过 7 节，每个结点又可以有上下左右四个方向（2位）移动，

   所以头结点处在 (x, y) 时，贪吃蛇的的状态可以用 7 * 2 = 14 位来表示，每个结点占 2 位;

2. 设计好状态之后另外一个难点就是，如果从 状态 -> 贪吃蛇坐标 的变换，其实就是涉及到一点位运算的知识，注意几个函数中上下左右的协调即可;

3. 通过 1,2 然后再采用宽搜，肯定能得到结果，不过会超时。这里采用启发式的搜索，估价函数为曼哈顿距离，其实提前用 bfs 预处理每个点到 (1, 1) 的最短路也是可以的;

4. 上面几点已经能够很好的 AC 了，不过还有更加值得优化的地方，找到贪吃蛇到达 (1, 1) 的最小最大距离，利用这个上界进行剪枝，又可以对时间有很高的飞跃;

5. 最终下面的代码跑到了 297ms 。其实还有很多可以优化的地方，因为本题的空间存在着很大的浪费，估价函数还可以进一步优化等等，有人是跑到了 0ms 的，所以还需努力.

 

#include 
    
     #include 
     
      #include 
      
       using namespace std;bool vis[21][21][1<<14];bool stone[21][21];int row, col, L, K;const int dir[4][2] = {
     -1, 0, 1, 0, 0, -1, 0, 1};struct Body {
         int x, y;} body[10];struct ST {
         int x, y, step, state, f;    ST(int _x, int _y, int _step, int _state, int _f)         : x(_x), y(_y), step(_step), state(_state), f(_f) {}    bool operator < (const ST& other) const {
      return f > other.f; }};void setstone() {
         for (int i = 1; i < L; i++)        stone[body[i].x][body[i].y] = true;}void clearstone() {
         for (int i = 1; i < L; i++)        stone[body[i].x][body[i].y] = false;}int getstate(int x, int y) {
         int state = 0;    for (int i = 1; i < L; i++) {
             state <<= 2;        if (body[i].x > body[i-1].x)        // up            state |= 0;             else if (body[i].x < body[i-1].x)   // down            state |= 1;        else if (body[i].y > body[i-1].y)   // left            state |= 2;        else if (body[i].y < body[i-1].y)   // right            state |= 3;    }    return state;}void setbody(int x, int y, int state) {
         const int MASK = 3;    body[0].x = x, body[0].y = y;    for (int i = 1; i < L; i++) {
             int val = (state >> ((L-i-1)*2)) & MASK;        body[i].x = body[i-1].x;        body[i].y = body[i-1].y;        if (val == 0) body[i].x += 1;        else if (val == 1) body[i].x -= 1;        else if (val == 2) body[i].y += 1;        else if (val == 3) body[i].y -= 1;    }}bool judge(int x, int y) {
         if (0 < x && x <= row && 0 < y && y <= col && !stone[x][y]) {
             return true;    }    return false;}inline int getdiff(int x, int y) {
         return abs(x - 1) + abs(y - 1);}int astar() {
         priority_queue
       
         Q;    int x = body[0].x, y = body[0].y;    int state = getstate(x, y);    int f = getdiff(x, y);    Q.push(ST(x, y, 0, state, f));    vis[x][y][state] = true;    while (!Q.empty()) {
             ST u = Q.top();        Q.pop();        if (u.x == 1 && u.y == 1)            return u.step;        setbody(u.x, u.y, u.state);        setstone();        for (int i = 0; i < 4; i++) {
                 x = u.x + dir[i][0];            y = u.y + dir[i][1];            state = (L<2) ? 0 : (u.state>>2) | (i<<((L-2)*2));            if (judge(x, y) && !vis[x][y][state]) {
                     vis[x][y][state] = true;                f = u.step + 1 + getdiff(x, y);                Q.push(ST(x, y, u.step + 1, state, f));            }        }        clearstone();    }    return -1;}int bfs() {
         bool visit[21][21];    memset(visit, false, sizeof(visit));    priority_queue
        
          Q;    int x = body[0].x, y = body[0].y;    int f = getdiff(x, y);    Q.push(ST(x, y, 0, 0, f));    visit[x][y] = true;    while (!Q.empty()) {
             ST u = Q.top();        Q.pop();        if (u.x == 1 && u.y == 1)            return u.step;        for (int i = 0; i < 4; i++) {
                 x = u.x + dir[i][0];            y = u.y + dir[i][1];            if (judge(x, y) && !visit[x][y]) {
                     visit[x][y] = true;                f = u.step + 1 + getdiff(x, y);                Q.push(ST(x, y, u.step + 1, 0, f));            }         }    }    return -1;}int main() {
         int cases = 0;    while (scanf("%d%d%d", &row, &col, &L) && row && col && L) {
             for (int i = 0; i < L; i++)            scanf("%d%d", &body[i].x, &body[i].y);         for (int i = 1; i <= row; i++) {
                 for (int j = 1; j <= col; j++) {
                     stone[i][j] = false;                memset(vis[i][j], false, sizeof(vis[0][0]));            }        }        scanf("%d", &K);        for (int i = 0; i < K; i++) {
                 int x, y;            scanf("%d%d", &x, &y);            stone[x][y] = true;        }        int ans;        int minstep = bfs();        setstone();        int maxstep = bfs();        clearstone();        if (minstep == -1)             ans = -1;        else if (minstep == maxstep)            ans = minstep;        else            ans = astar();        printf("Case %d: %d\n", ++cases, ans);    }    return 0;}