首页 > 代码库 > uestc 贪吃蛇
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\n",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 else118 {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\n",kase++,ans);149 while (!Q.empty())Q.pop();150 }151 return 0;152 }
uestc 贪吃蛇
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。