問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324參考:
http://hi.baidu.com/aekdycoin/blog/item/08774afbd1a29316a8d31111.htmlhttp://clover520.blogbus.com/logs/38001465.html思路:
用BFS求最短路徑肯定是沒有問題的，關鍵是狀態如何表示
參考別人的思路，原來蛇身只需要通過上、下、左、右四個方向表示即可(兩bits或4進制)，這樣可以很大程度上減少空間，而且判重也就不再是個問題，只需要用三維數組表示即可
不過我自己寫出來的代碼卻總是MLE，悲劇...(無奈，貼了別人代碼過的，無恥啊)
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4
5 int kk[4][2]={1,0,0,1,0,-1,-1,0},N,M,L;
6 struct point{
7 char x,y;
8 int dis,body;
9 };
10 int bfs();
11 int main(){
12 int Cas=0;
13 while(scanf("%d%d%d",&N,&M,&L)==3){
14 if(N==0&&M==0&&L==0)break;
15 printf("Case %d: %d\n",++Cas,bfs());
16 }
17 return 0;
18 }
19 char viss[20][20][1<<14];
20 int vis(struct point* t){
21 int ans=0,i=0;
22 if(viss[t->x][t->y][t->body])return 1;
23 viss[t->x][t->y][t->body]=1;
24 return 0;
25 }
26 char map[20][20],mapt[20][20];
27 char valid(int x,int y){
28 if(x<0||x>=N||y<0||y>=M||mapt[x][y])return 0;
29 return 1;
30 }
31 struct point Q[20*20*(1<<14)];
32 int head,tail;
33 int bfs(){
34 int x,y,lx,ly,i,k,nx,ny;
35 struct point t,now;
36 memset(viss,0,sizeof(viss));
37 scanf("%d%d",&lx,&ly);
38 t.x=lx-1;t.y=ly-1;t.dis=0;t.body=0;
39 for(i=1;i<L;++i){
40 scanf("%d%d",&x,&y);
41 for(k=0;k<4;++k)if(lx+kk[k][0]==x&&ly+kk[k][1]==y)break;
42 t.body|=k<<((i-1)<<1);
43 lx=x;ly=y;
44 }
45 memset(map,0,sizeof(map));
46 scanf("%d",&k);
47 for(i=0;i<k;++i){
48 scanf("%d%d",&x,&y);
49 map[x-1][y-1]=1;
50 }
51 head=tail=0;
52 Q[tail++]=t;
53 vis(&t);
54 while(head!=tail){
55 now=Q[head++];
56 if(now.x==0&&now.y==0)return now.dis;
57
58 memcpy(mapt,map,sizeof(map));
59 mapt[x=now.x][y=now.y]=1;
60 int s=now.body;
61 for(i=1;i<L;++i,s>>=2){
62 k=s&3;
63 mapt[x=x+kk[k][0]][y=y+kk[k][1]]=1;
64 }
65
66 for(k=0;k<4;++k){
67 if(!valid(nx=now.x+kk[k][0],ny=now.y+kk[k][1]))continue;
68 t.x=nx,t.y=ny;
69 t.body=((now.body<<2)|(3-k))&((1<<((L-1)<<1))-1);
70 t.dis=now.dis+1;
71 if(!vis(&t)){
72 Q[tail++]=t;
73 }
74 }
75 }
76 return -1;
77 }