Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA了n发,内存爆了无数次,终于A了!/* 内存爆的原因开始是因为没有用状态压缩,直接用数组表示贪吃蛇,内存过大, 改了之后任然爆,是因为没有用vis标记已访问点, WA了n多次是因为vis标记数组应该在新的状态下判断,而不是队头的状态(估计只有我这种菜鸡才会犯这个错吧), 看下我的代码吧,写的很凌乱,将就看。 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; bool map[21][21];//地图 bool vis[21][21][1<<14]; typedef struct { int x,y; //坐标 int state; //蛇身状态 int step; //走的步数 }Point; int dxy[4][2]={ 1,0, //下 -1,0, //上 0,1, //右 0,-1 //左 }; int m,n,L,K; int beginState; int headx,heady; // 广度优先搜索 int bfs() { queue<Point>P; Point root;//根 memset(vis,0,sizeof(vis)); root.state = beginState; root.step=0; root.x = headx;root.y=heady; P.push(root); while (!P.empty()) { Point f = P.front(); if(f.x==1&&f.y==1) return f.step;//达到目的地,结束 for(int i=0;i<4;i++){ int dx=f.x+dxy[i][0];// 新的坐标点 int dy=f.y+dxy[i][1]; int tx=f.x,ty=f.y; bool pass = false; for(int k=L-2;k>=0;k--) { //当前点是蛇身体 tx+=dxy[(f.state>>(2*k))%4][0]; ty+=dxy[(f.state>>(2*k))%4][1]; if(dx==tx&&dy==ty){ pass = true; break; } } if(pass||dx<=0||dx>n||dy<=0||dy>m||map[dx][dy]) continue; Point newHead=f; newHead.x = dx; newHead.y = dy; newHead.step = f.step+1;//步数加一 //更新蛇头,丢掉蛇尾 newHead.state = ((i/2*2+(!(i%2)))<<(2*L-4))+(newHead.state>>2); if(!vis[dx][dy][newHead.state]) { P.push(newHead); vis[dx][dy][newHead.state]=1; } } P.pop();//队头出队 } return -1;//不能达到终点 } int main() { int cnt=1; int x,y; while (cin>>n>>m>>L){ beginState=0; if(n==0&&m==0&&L==0)break; memset(map,0,sizeof(map)); for(int i=0;i<L;i++){ int dx,dy; cin>>dx>>dy; if(i==0){ headx = dx; heady = dy; }else{ for(int k=0;k<4;k++){ if(((dx-x)==dxy[k][0])&&((dy-y)==dxy[k][1])){ beginState<<=2; beginState += k; } } } x=dx;y=dy; } cin>>K; for(int i=0;i<K;i++) { cin>>x>>y; map[x][y]=true;//表示障碍 } cout<<"Case "<<cnt++<<":"<<" "; cout<<bfs()<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator