| ||||||||||
| 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 | |||||||||
bfsA的艰难啊
#include<iostream>
#include<queue>
using namespace std;
char map[400][400];
int m,n;
int x1,y1;
int x2,y2;
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool visit[400][400];
struct note
{
int x;
int y;
int turn;
};
void bfs()
{
queue<note> q;
int front=0,rear=0;
note current,next;
current.x=x1;
current.y=y1;
current.turn=0;
q.push(current);
visit[x1][y1]=true;
int i;
bool p=false;
while(!q.empty())
{
current=q.front();
q.pop();
if(current.x==x2&¤t.y==y2) {p=true;break;}
if(map[current.x][current.y]=='B')
{
current.turn++;
q.push(current);
map[current.x][current.y]='E';
}
else
{
for(i=0;i<4;i++)
{
next.x=current.x+move[i][0];
next.y=current.y+move[i][1];
if(next.x>=0&&next.x<m&&next.y>=0&&next.y<n&&!visit[next.x][next.y]&&map[next.x][next.y]!='S'&&map[next.x][next.y]!='R')
{
next.turn=current.turn+1;
q.push(next);
visit[next.x][next.y]=true;
}
}
}
}
if(!p) printf("-1\n");
else printf("%d\n",current.turn);
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(visit,false,sizeof(visit));
if(m==0&&n==0) break;
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
cin>>map[i][j];
if(map[i][j]=='Y')
{
x1=i;
y1=j;
}
else if(map[i][j]=='T')
{
x2=i;
y2=j;
}
}
bfs();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator