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