2 shlsjk shlsjk 于 2014.11.06 16:09 提问

ACM北大POJ_1376代码提交一直WA,求大神看看哪里错了?呜呜

#include
#include
#include
using namespace std;
bool Map[55][55];
bool vis[55][55][4]; //[4] 四个directions,坐标和方向都相同时不能同时经过该点两次;
int M,N;
bool flag=false; //找到路径置为true;
typedef struct
{
int x,y; //坐标;
int time; //走到当前格子所用时间;
int dir; //当前格子所朝方向;
}point;

point Start,End;
bool canPass(int x,int y,int direction)
{
if(x<=0||x>=M||y<=0||y>=N) //走到边界;
return false;
if(vis[x][y][direction]|| !Map[x][y]|| !Map[x+1][y]|| !Map[x][y+1]||!Map[x+1][y+1])
return false;
else
return true;
}
void bfs()
{
point temp,temp1;
queue q;
while(!q.empty()) //调用完后要清空队列;
q.pop();
int dir1,dir2;
q.push(Start);
vis[Start.x][Start.y][Start.dir]=true;
while(!q.empty())
{
temp=q.front();
q.pop();
if((temp.x==End.x)&&(temp.y==End.y)) //到达终点;
{
flag=true;
cout< return;
}
dir1=(temp.dir+1)%4; //0为south,1为east,2为north,3为west,每次转90度刚好dir+1或dir-1对4取余即可
dir2=(temp.dir-1+4)%4;
temp1=temp;
if(!vis[temp1.x][temp1.y][dir1]) //相同点不同方向没有访问过则入队;
{
vis[temp1.x][temp1.y][dir1]=true;
temp1.dir=dir1;
temp1.time++;
q.push(temp1);
}
temp1=temp;
if(!vis[temp1.x][temp1.y][dir2])
{
vis[temp1.x][temp1.y][dir2]=true;
temp1.dir=dir2;
temp1.time++;
q.push(temp1);
}
for(int i=0;i {
switch(temp.dir)
{
case 0: temp.x++; break;
case 1: temp.y++; break;
case 2: temp.x--; break;
case 3: temp.y--; break;
}
if(!canPass(temp.x,temp.y,temp.dir))
break;
else
{
vis[temp.x][temp.y][temp.dir]=true;
if(i==0)
temp.time++; //走1,2,3步都只需要耗时1秒,只需要第一次走一步时间加1就行;
q.push(temp);
}
}
}
}
int main()
{
int t;
string s;
while(cin>>M>>N&&(M||N))
{
memset(Map,false,sizeof(Map));
memset(vis,false,sizeof(vis));
flag=false;
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
{
cin>>t;
Map[i][j]=t==0?true:false; //true(0)表示可以通行,false(1)表示不能走;
}
}
cin>>Start.x>>Start.y>>End.x>>End.y;
cin>>s;
if(!canPass(Start.x,Start.y,Start.dir) ||!canPass(End.x,End.y,End.dir))
{
cout<<"-1"<<endl;
continue; //起始点和终点如果在边界或本身是障碍物则直接输出-1返回;
}
if(s=="south")
Start.dir=0;
else if(s=="east")
Start.dir=1;
else if(s=="north")
Start.dir=2;
else if(s=="west")
Start.dir=3;
bfs();
if(flag==false)
cout<<"-1"<<endl;
}
return 0;
}

1个回答

happyparrot
happyparrot   Ds   Rxr 2015.01.27 08:25

这么长的代码,怎么看啊。自己有调试过吗?

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!