问题描述

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

解决方案

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