| ||||||||||
| 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