POJ 1324 Holedox Moving

题意：给出蛇头和蛇身（蛇身分为若干节，用坐标连起来，当然蛇头也是一个坐标）
给出终点坐标，障碍物坐标，问蛇能不能到达终点（蛇头到达）

本题可以用状态压缩，表示蛇头在x,y，蛇身的状态。蛇身的状态可以用该部分和上一部分的相对位置来表示，分别有四种状态就是在它的上下左右，分别记为0，1，2，3，二进制位是00，01，10，11。蛇身长共7节，7*2也就是14位，空间足够，然后一节一节广搜就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<bitset>
using std::bitset;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct edge {
    int st,x[10],y[10],sta;
    bitset<23> d[23];
    edge (){
        st=sta=0;
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
    }
};
int map[24][24];
int n,m,l,k,v[22][22][1<<15];
int ch[5][5];
inline int check(edge now,int x,int y){
    int sta=0;
    for(int i=2;i<=l;++i){
        int temp=0;
        temp=ch[now.x[i]-now.x[i-1]+1][now.y[i]-now.y[i-1]+1];
        sta|=temp<<((i-1)*2);
    }
    if(v[x][y][sta]) return 0;
    v[x][y][sta]=1;
    return 1;
}
inline edge copy(edge old,int x,int y){
    edge nwe;
    for(int i=2;i<=l;++i){
        nwe.x[i]=old.x[i-1];
        nwe.y[i]=old.y[i-1];
    }
    for(int i=1;i<=n;++i) nwe.d[i]=old.d[i];
    nwe.st=old.st+1;
    nwe.d[old.x[l]][old.y[l]]=0;
    nwe.x[1]=x,nwe.y[1]=y;
    nwe.d[x][y]=1;
    return nwe;
}
inline int BFS(edge star){
    std::queue<edge> q;
    while(!q.empty()) q.pop(); 
    q.push(star);
    while(!q.empty()){
        edge now=q.front();q.pop();
        if(now.x[1]==1&&now.y[1]==1) return now.st;
        for(int i=0;i<=3;++i){
            int gx=dx[i]+now.x[1];
            int gy=dy[i]+now.y[1];
            if(now.d[gx][gy]==1) continue;
            if(gx<=0||gy<=0||gx>n||gy>m) continue;
            if(check(now,gx,gy)){
                edge nwe=copy(now,gx,gy);
                if(gx==1&&gy==1) return nwe.st;
                q.push(nwe);
            }
        }
    }
    return 0x3f3f3f3f;
}
int main (){
    int T=0;
    ch[-1+1][0+1]=1;
    ch[1+1][0+1]=2;
    ch[0+1][1+1]=4;
    ch[0+1][-1+1]=4;
    while(scanf("%d %d %d",&n,&m,&l)){
        T++;
        memset(v,0,sizeof(v));
        memset(map,0,sizeof(map));
        if(n==0&m==0&l==0) return 0;
        edge st;
        for(int j=1;j<=l;++j)
            for(int i=1;i<=l;++i)
                 st.d[i][j]=0;
        for(int i=1;i<=l;++i){
            int x,y,z=0;
            scanf("%d %d",&x,&y);
            st.d[x][y]=1;
            st.x[i]=x,st.y[i]=y;
            if(i!=1)
                z=ch[st.x[i]-st.x[i-1]+1][st.y[i]-st.y[i-1]+1];
            st.sta|=z<<((i-1)*2);
        }
        v[st.x[1]][st.y[1]][st.sta]=1;
        scanf("%d",&k);
        while(k--){
            int x,y;
            scanf("%d %d",&x,&y);
            st.d[x][y]=1;
            map[x][y]=1;
        }
        int ans=BFS(st);
        if(ans!=0x3f3f3f3f){
            printf("Case %d: %d\n",T,ans);
        }
        else{
            printf("Case %d: %d\n",T,-1);
        }
    }

    return 0;
}