题目地址：http://poj.org/problem?id=1324
写了一天了 ，一开始想表示状态用头和尾位置，但很快写出来就WR
然后就用根据贪吃蛇的节点与上一个节点位置关系保存状态，一共有4个状态，上下左右，0~3表示，正好二进制占两个位
最多有14个状态，所以int就可以保存
然后写出来后MLE然后TLE然后MLE然后TLE然后WR.... 不容易啊woc...
最后发现vector太慢了，果断用数组，再重写一遍
然后发现h()定义有很大问题，再改
还有不同h()计算方式不行，h()一定要体现h()+g()最小离终点最近,这样才会正确
所以单单把h()*100是不行的，因为有种可能会导致h()小但g()很大的排在队列前面
h()定义法则如下：
我选的是以头节点离终点的曼哈顿距离为h(), 这样肯定相容
代码如下：23864K 1672MS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=20+5;
struct Node{int x,y,snack,f,g,h;Node(int x=0,int y=0,int s=0,int g=0,int h=0):x(x),y(y),snack(s),f(g+h),g(g),h(h){}bool operator < (const Node& n) const {if(f==n.f) return g>n.g;return f>n.f;}
};
struct Snack{int x[10],y[10];
};
bool closed[maxn][maxn][1<<15];
int R,C,m;
bool G[maxn][maxn];
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};int H(const Snack& s){int cnt=0;
// for(int i=0;i<m;i++)
// cnt+=(s.x[i]+s.y[i])*i*100; //头的比重大 cnt+=s.x[0]+s.y[0];return cnt*100;
}
bool inside(int x,int y){return x>=1&&x<=R&&y>=1&&y<=C;
}
int Encode(const Snack& s){int code=0;for(int i=m-1;i>=1;i--){int xt=find(dx,dx+4,s.x[i]-s.x[i-1])-dx;int yt=find(dy,dy+4,s.y[i]-s.y[i-1])-dy;int t=max(xt,yt);code<<=2; code|=t;}return code;
}
Snack Decode(int x,int y,int s){Snack ns;ns.x[0]=x,ns.y[0]=y;for(int i=1;i<m;i++){int t=3; t&=s;ns.x[i]=ns.x[i-1]+dx[t];ns.y[i]=ns.y[i-1]+dy[t];s>>=2;}return ns;
}
Node move(Node s,int i){ //i=up down left rightint x=s.x+dx[i];int y=s.y+dy[i];int t=i^1; //反方向 int snack=s.snack;snack<<=2; snack|=t; snack&=((1<<((m-1)*2))-1); //去掉最高位 int h=H(Decode(x,y,snack));return Node(x,y,snack,s.g+1,h);
}
bool bCross(int x,int y,int s,int i){int nx=x+dx[i];int ny=y+dy[i];if(!inside(nx,ny)||G[nx][ny]) return false;Snack snack=Decode(x,y,s);for(int i=1;i<m;i++)if(nx==snack.x[i]&&ny==snack.y[i]) return false;return true;
}
bool inClosed(Node s){if(closed[s.x][s.y][s.snack]) return true;closed[s.x][s.y][s.snack]=true;return false;
}
int A_star(Node start)
{memset(closed,false,sizeof(closed));priority_queue<Node> open;open.push(start);inClosed(start);while(!open.empty()){Node s=open.top(); open.pop();if(s.x==1&&s.y==1) return s.g;for(int i=0;i<4;i++){if(!bCross(s.x,s.y,s.snack,i)) continue; Node ns=move(s,i);if(inClosed(ns)) continue;else open.push(ns);}}return -1;
}
int main()
{int n,x,y,kase=0; Snack snack;while(scanf("%d%d%d",&R,&C,&m)!=EOF){if(R==0&&C==0&&m==0) break;for(int i=0;i<m;i++){ scanf("%d%d",&x,&y);snack.x[i]=x;snack.y[i]=y;}scanf("%d",&n);memset(G,false,sizeof(G));for(int i=0;i<n;i++){scanf("%d%d",&x,&y);G[x][y]=true;}Node s=Node(snack.x[0],snack.y[0],Encode(snack),0,H(snack));printf("Case %d: %d\n",++kase,A_star(s));}return 0;
}