poj 1324 状态广搜

其实就是我们经常玩的贪吃蛇。
不过现在我们优先蛇的头的话，要用一个巧妙的哈希来把蛇的身体表达出来，那么就可以用一个4进制的数字来表示，蛇的身体长度最多不超过8，所以最多是2^7种状态。
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<cmath>
  6 int const N = 8;
  7 int const M = 22;
  8 int const State = 17000;
  9 struct Snake
 10 {
 11        int bx[N],by[N];
 12        int step;
 13 }cur,nt;
 14 Snake q[1000000];
 15 int head,tail;
 16 int n,m,l,x,y,ans,s;
 17 bool map[M][M],vis[M][M][State];
 18 int dirx[]={0,0,-1,1};
 19 int diry[]={-1,1,0,0};
 20 bool judge(int x,int y)
 21 {
 22      return x<1||x>n||y<1||y>m||map[x][y];
 23 }
 24 int check(int x1,int y1,int x2,int y2)
 25 {
 26     if(x1==x2)
 27     {
 28        if(y1>y2)
 29           return 0;
 30        else
 31           return 1;
 32     }
 33     else
 34     {
 35        if(x1>x2)
 36           return 2;
 37        else
 38           return 3;
 39     }
 40 }
 41 int bfs()
 42 {
 43      cur.step=0;
 44      int state=0;
 45      for(int j=0;j<l-1;j++)
 46          state=state*4+check(cur.bx[j],cur.by[j],cur.bx[j+1],cur.by[j+1]);
 47      vis[cur.bx[0]][cur.by[0]][state]=true;
 48      head=tail=0;
 49      q[tail++]=cur;
 50      while(head<tail)
 51      {
 52            cur=q[head++];
 53            if(cur.bx[0]==1&&cur.by[0]==1)return cur.step;
 54            for(int i=0;i<4;i++)
 55            {
 56                nt.bx[0]=cur.bx[0]+dirx[i];
 57                nt.by[0]=cur.by[0]+diry[i];
 58                nt.step=cur.step+1;
 59                if(judge(nt.bx[0],nt.by[0]))continue;
 60                int f=0;
 61                for(int j=0;j<l;j++)
 62                    if(nt.bx[0]==cur.bx[j]&&nt.by[0]==cur.by[j])
 63                    {
 64                       f=1;break;
 65                    }
 66                if(f)continue;
 67                for(int j=l-1;j>0;j--)
 68                    nt.bx[j]=cur.bx[j-1],nt.by[j]=cur.by[j-1];
 69                int state=0;
 70                for(int j=0;j<l-1;j++)
 71                    state=state*4+check(nt.bx[j],nt.by[j],nt.bx[j+1],nt.by[j+1]);
 72                if(!vis[nt.bx[0]][nt.by[0]][state])
 73                {
 74                   vis[nt.bx[0]][nt.by[0]][state]=true;
 75                   q[tail++]=nt;
 76                }
 77            }
 78      }
 79      return -1;
 80 }
 81 int main()
 82 {
 83     int T=0;
 84     while(~scanf("%d %d %d",&n,&m,&l)&&(n+m+l)!=0)
 85     {
 86           for(int i=1;i<=n;i++)
 87              for(int j=1;j<=n;j++)
 88              {
 89                  map[i][j]=false;
 90                  for(int k=0;k<=(1<<(2*(l-1)));k++)
 91                      vis[i][j][k]=false;
 92              }
 93           for(int i=0;i<l;i++)
 94               scanf("%d %d",&cur.bx[i],&cur.by[i]);
 95           scanf("%d",&s);
 96           for(int i=0;i<s;i++)
 97           {
 98               scanf("%d %d",&x,&y);
 99               map[x][y]=true;
100           }
101           printf("Case %d: %d
",++T,bfs());
102     }
103     return 0;
104 }
View Code