| ||||||||||
| 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 | |||||||||
贡献1WA//从B出发时,把B换成E,step+1,形成一个新的结点加入到队列中去
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int to[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
struct Point
{
int r,c;
int step;
};
int r,c;
char maps[305][305];
bool vis[305][305];
bool judge (int rx,int cx)
{
if(rx<0||rx>=r||cx<0||cx>=c||maps[rx][cx]=='S'||maps[rx][cx]=='R'||vis[rx][cx])
return true;
else return false;
}
int main()
{
int sr,sc;
while(scanf("%d%d",&r,&c),r)
{
memset(vis,false,sizeof(vis));
for(int i=0; i<r; i++)
{
scanf("%s",maps[i]);
for(int j=0; j<c; j++)
{
if(maps[i][j]=='Y')
{
sr = i;
sc = j;
}
}
}
int ans = -1;
queue<Point> Q;
Point a,next;
a.r = sr;
a.c = sc;
a.step = 0;
vis[a.r][a.c] = true;
Q.push(a);
while(!Q.empty())
{
a = Q.front();
Q.pop();
if(maps[a.r][a.c]=='T')
{
ans = a.step;
break;
}
if(maps[a.r][a.c]=='B')
{
a.step ++;
maps[a.r][a.c] = 'E';
Q.push(a);
continue;
}
for(int i=0; i<4; i++)
{
next.r = a.r + to[i][0];
next.c = a.c + to[i][1];
if(judge(next.r,next.c))
continue;
vis[next.r][next.c] = true;
next.step = a.step +1;
Q.push(next);
}
}
printf("%d\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator