| ||||||||||
| 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 | |||||||||
终于AC了 47ms贡献了三个WA,原来是边界的判断写错了一个数字
#include <stdio.h>
#include <memory.h>
#include <queue>
#define MAXN 301
#define INF 0x3f3f3f3f
using namespace std;
typedef struct
{ int x;
int y;
}Point;
Point de[MAXN][MAXN],you;
int dis[MAXN][MAXN],visited[MAXN][MAXN];
int N,M;
char G[MAXN][MAXN];
int Distance(int i,int j)
{ if(G[i][j]=='B') return 2;
return 1;
}
bool Judge(int x,int y)
{ if(G[x][y]=='S'||G[x][y]=='R')
return false;
if(x<1||x>N||y<1||y>M)
return false;
return true;
}
void spfa()
{ queue<Point>q;
Point temp,semp;
int i,j,x,y,t;
memset(visited,0,sizeof(visited));
memset(dis,0x3f,sizeof(dis));
q.push(you),visited[you.x][you.y]=1,dis[you.x][you.y]=0;
while(!q.empty())
{ temp=q.front();
q.pop();
visited[temp.x][temp.y]=0;
for(i=1;i<=4;++i)
{ if(i==1&&Judge(temp.x-1,temp.y))
{ if(dis[temp.x-1][temp.y]>(t=dis[temp.x][temp.y]+
Distance(temp.x-1,temp.y)))
{ dis[temp.x-1][temp.y]=t;
if(!visited[temp.x-1][temp.y])
{ visited[temp.x-1][temp.y]=1;
semp=temp;
semp.x--;
q.push(semp);
}
}
}
else if(i==2&&Judge(temp.x,temp.y-1))
{ if(dis[temp.x][temp.y-1]>(t=dis[temp.x][temp.y]+
Distance(temp.x,temp.y-1)))
{ dis[temp.x][temp.y-1]=t;
if(!visited[temp.x][temp.y-1])
{ visited[temp.x][temp.y-1]=1;
semp=temp;
semp.y--;
q.push(semp);
}
}
}
else if(i==3&&Judge(temp.x+1,temp.y))
{ if(dis[temp.x+1][temp.y]>(t=dis[temp.x][temp.y]+
Distance(temp.x+1,temp.y)))
{ dis[temp.x+1][temp.y]=t;
if(!visited[temp.x+1][temp.y])
{ visited[temp.x+1][temp.y]=1;
semp=temp;
semp.x++;
q.push(semp);
}
}
}
else if(i==4&&Judge(temp.x,temp.y+1))
{ if(dis[temp.x][temp.y+1]>(t=dis[temp.x][temp.y]+
Distance(temp.x,temp.y+1)))
{ dis[temp.x][temp.y+1]=t;
if(!visited[temp.x][temp.y+1])
{ visited[temp.x][temp.y+1]=1;
semp=temp;
semp.y++;
q.push(semp);
}
}
}
}
}
}
int main()
{ int i,j;
Point target;
while(scanf("%d %d",&N,&M)!=EOF)
{ if(N==0&&M==0) break;
getchar();
for(i=1;i<=N;++i)
{ for(j=1;j<=M;++j)
{ scanf("%c",&G[i][j]);
if(G[i][j]=='Y') you.x=i,you.y=j;
else if(G[i][j]=='T') target.x=i,target.y=j;
}
getchar();
}
spfa();
if(dis[target.x][target.y]!=INF)
printf("%d\n",dis[target.x][target.y]);
else puts("-1");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator