uestc 贪吃蛇

转自：http://m.blog.csdn.net/blog/u013776011/25992865

贪吃蛇，首要问题是如何记录蛇的状态，蛇头，蛇身中每个点与上一点之间的方向关系。
故可以用哈希来定义状态,这里学习了别人的hash方法。每次找到当前点与前面一点的方向关系来确定hash返回值
剩下的就是直接BFS，每次更新新蛇一定要注意蛇的长度是多少，如果蛇的长度大于等于3，那么碰到蛇的尾部是合法的
如果蛇的长度小于3，那么碰到蛇尾是不合法的
另外注意移动过程中那种情况下都不能碰到蛇身
利用蛇前后位置的一一替换的对应关系，移动蛇身。根据hash判重就可以
每组数据后要清空队列

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <queue>
  7 #define Mod 1000000007
  8 #define ll long long
  9 using namespace std;
 10 #define N 107
 11 
 12 struct Point
 13 {
 14     int x,y;
 15 }p[11];
 16 
 17 struct node
 18 {
 19     int x,y;
 20     int num,step;
 21 }S;
 22 
 23 char mp[17][17];
 24 int vis[70000][16][16];
 25 int R,C,K;
 26 int EX,EY;
 27 int dx[4] = {1,0,0,-1};
 28 int dy[4] = {0,1,-1,0};
 29 
 30 int p_to_num(Point *p)
 31 {
 32     int i,k;
 33     int res = 0,now = 0;
 34     for(i=1;i<K;i++)
 35     {
 36         int sx = p[i].x;
 37         int sy = p[i].y;
 38         int tx = p[i+1].x;
 39         int ty = p[i+1].y;
 40         if(sx > tx && sy == ty)
 41             k = 3;   //下
 42         else if(sx == tx && sy > ty)
 43             k = 2;   //右
 44         else if(sx < tx && sy == ty)
 45             k = 0;   //上
 46         else if(sx == tx && sy < ty)
 47             k = 1;   //左
 48         k <<= now;
 49         now += 2;
 50         res |= k;
 51     }
 52     return res;
 53 }
 54 
 55 bool OK(int nx,int ny)
 56 {
 57     if(nx >= 0 && nx < R && ny >= 0 && ny < C)
 58         return true;
 59     return false;
 60 }
 61 
 62 bool check(int num)
 63 {
 64     int i,j,k;
 65     k = K-1;
 66     int x = 0,y = 0;
 67     while(k--)
 68     {
 69         x += dx[num&3];
 70         y += dy[num&3];
 71         if(x == 0 && y == 0)
 72             return false;
 73         num >>= 2;
 74     }
 75     return true;
 76 }
 77 
 78 int BFS(node S)
 79 {
 80     int i,j,k;
 81     queue<node> que;
 82     memset(vis,0,sizeof(vis));
 83     que.push(S);
 84     vis[S.num][S.x][S.y] = 1;
 85     int MOD = (1<<((K-1)*2));
 86     while(!que.empty())
 87     {
 88         node tmp = que.front();
 89         que.pop();
 90         if(tmp.x == EX && tmp.y == EY)
 91             return tmp.step;
 92         for(i=0;i<4;i++)
 93         {
 94             if(K <= 1 || ((tmp.num&3) != i))
 95             {
 96                 int nx = tmp.x + dx[i];
 97                 int ny = tmp.y + dy[i];
 98                 if(!OK(nx,ny) || mp[nx][ny] == '#')
 99                     continue;
100                 node now;
101                 now.num = (tmp.num << 2);
102                 now.num |= (3-i);
103                 now.num %= MOD;
104                 if(vis[now.num][nx][ny])   //状态已走过
105                     continue;
106                 if(!check(now.num))    //咬到蛇身
107                     continue;
108                 vis[now.num][nx][ny] = 1;
109                 now.x = nx;
110                 now.y = ny;
111                 now.step = tmp.step + 1;
112                 que.push(now);
113             }
114         }
115     }
116     return -1;
117 }
118 
119 int main()
120 {
121     int i,j,k,cs = 1;
122     while(scanf("%d%d",&R,&C)!=EOF)
123     {
124         K = 1;
125         for(i=0;i<R;i++)
126         {
127             scanf("%s",mp[i]);
128             for(j=0;j<C;j++)
129             {
130                 if(mp[i][j] == '@')
131                     EX = i,EY = j;
132                 if(mp[i][j] >= '1' && mp[i][j] <= '9')
133                 {
134                     k = mp[i][j] - '0';
135                     p[k].x = i,p[k].y = j;
136                     K = max(K,k);
137                 }
138             }
139         }
140         S.num = p_to_num(p);
141         S.x = p[1].x;
142         S.y = p[1].y;
143         S.step = 0;
144         printf("Case #%d: %d
",cs++,BFS(S));
145     }
146     return 0;
147 }

代码君

  1 #include <map>
  2 #include <set>
  3 #include <list>
  4 #include <cmath>
  5 #include<cctype>
  6 #include <ctime>
  7 #include <deque>
  8 #include <stack>
  9 #include <queue>
 10 #include <cstdio>
 11 #include <string>
 12 #include <vector>
 13 #include <cstdlib>
 14 #include <cstring>
 15 #include <iostream>
 16 #include <algorithm>
 17 #define LL long long
 18 #define PI 3.1415926535897932626
 19 using namespace std;
 20 int gcd(int a, int b)
 21 {
 22     return a % b == 0 ? b : gcd(b, a % b);
 23 }
 24 char G[20][20];
 25 int vis[20000000];
 26 int dx[]={1,0,-1,0};
 27 int dy[]={0,1,0,-1};
 28 int len;
 29 int N,M;
 30 int e_x,e_y,s_x,s_y;
 31 int ans;
 32 struct node
 33 {
 34     int x[11],y[11];//存蛇的每一个点的横纵坐标
 35     int dist;
 36 }s;
 37 queue<node>Q;
 38 int get_nextdir(int cur,int pre,node s)
 39 {
 40     for (int d=0;d<4;d++)
 41     {
 42         int nx=s.x[pre]+dx[d];
 43         int ny=s.y[pre]+dy[d];
 44         if (nx==s.x[cur] && ny==s.y[cur]) return d;
 45     }
 46 }
 47 int hash(int x,int y,node s)
 48 {
 49     int Hash=x*M+y;
 50     for (int i=1;i<len;i++)
 51         {
 52             Hash=Hash*4+get_nextdir(i,i-1,s);
 53         }
 54         return (Hash%20000000);
 55 }
 56 void read()
 57 {
 58     len=0;
 59     ans=-1;
 60     memset(G,0,sizeof(G));
 61     memset(vis,0,sizeof(vis));
 62     for (int i=0;i<N;i++)
 63     scanf("%s",G[i]);
 64     for (int i=0;i<N;i++)
 65         for (int j=0;j<M;j++)
 66     {
 67         if (G[i][j]=='@') {e_x=i;e_y=j;}
 68         if (isdigit(G[i][j]))
 69         {
 70             if (G[i][j]=='1') {s_x=i;s_y=j;}
 71             s.x[G[i][j]-'1']=i;
 72             s.y[G[i][j]-'1']=j;
 73             G[i][j]='.';
 74             len++;
 75         }
 76     }
 77     s.dist=0;
 78     int T=hash(s_x,s_y,s);
 79     vis[T]=1;
 80     Q.push(s);
 81     //show();
 82 }
 83 void bfs()
 84 {
 85     while (!Q.empty())
 86     {
 87         node u=Q.front();
 88         Q.pop();
 89         if (u.x[0]==e_x && u.y[0]==e_y) {ans=u.dist;return ;}
 90         int x=u.x[0],y=u.y[0];
 91         for (int d=0;d<4;d++)
 92         {
 93             int nx=x+dx[d];
 94             int ny=y+dy[d];
 95             if (nx<0 || nx>=N || ny<0 || ny>=M || G[nx][ny]=='#') continue;
 96             bool flag=false;
 97             if (len>=3)
 98             {
 99              for (int i=1;i<len-1;i++)
100              if (nx==u.x[i] && ny==u.y[i]) {flag=true;break;}
101              if (flag) continue;
102              node s;
103              s.x[0]=nx;s.y[0]=ny;
104              for (int i=1;i<len;i++)
105              {
106                 s.x[i]=u.x[i-1];
107                 s.y[i]=u.y[i-1];
108              }
109              LL T=hash(nx,ny,s);
110              if (!vis[T])
111              {
112                 vis[T]=1;
113                 s.dist=u.dist+1;
114                 Q.push(s);
115              }
116             }
117             else
118             {
119                 for (int i=1;i<=len-1;i++)//注意和上一种i<len-1不同
120              if (nx==u.x[i] && ny==u.y[i]) {flag=true;break;}
121              if (flag) continue;
122              node s;
123              s.x[0]=nx;s.y[0]=ny;
124              for (int i=1;i<len;i++)
125              {
126                 s.x[i]=u.x[i-1];
127                 s.y[i]=u.y[i-1];
128              }
129              LL T=hash(nx,ny,s);
130              if (!vis[T])
131              {
132                 vis[T]=1;
133                 s.dist=u.dist+1;
134                 Q.push(s);
135              }
136             }
137         }
138     }
139 }
140 int main()
141 {
142     //freopen("sample.txt","r",stdin);
143     int kase=1;
144     while (scanf("%d%d",&N,&M)!=EOF)
145     {
146         read();
147         bfs();
148         printf("Case #%d: %d
",kase++,ans);
149         while (!Q.empty())Q.pop();
150     }
151     return 0;
152 }

哈希版