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