http://acm.hdu.edu.cn/showproblem.php?pid=1242
有点简单的 BFS题目 唯一的不同 是X点可以 停滞一下
这次采取的方法与以前不同 对于X点的处理
注意 VIS【】【】记录是否访问和 走过此点的最短时间
#include<stdio.h> #include<string.h> #include<stdlib.h> char map[205][205]; int vis[205][205]; struct node { int x,y; int s; }dui[80005]; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int n,m,s_x,s_y; void bfs() { int i,j; int head,tail; struct node next,now; memset(vis,0,sizeof(vis)); head=tail=0; dui[tail].x=s_x; dui[tail].y=s_y; dui[tail++].s=1; vis[s_x][s_y]=1; while(head<tail) { now.x=dui[head].x; now.y=dui[head].y; now.s=dui[head++].s; if(map[now.x][now.y]=='x') { map[now.x][now.y]='.'; dui[tail].x=now.x; dui[tail].y=now.y; dui[tail++].s=now.s+1; continue; } for(i=0;i<4;i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; next.s=now.s+1; if( next.x<0 || next.y<0 || next.x>=n || next.y>=m || map[next.x][next.y]=='#') continue; if(vis[next.x][next.y]!=0) continue; vis[next.x][next.y]=next.s; dui[tail].x=next.x; dui[tail].y=next.y; dui[tail++].s=next.s; } } } int main() { int i,j,ans; while(scanf("%d%d",&n,&m)!=EOF) { ans=10000000; getchar(); for(i=0;i<n;i++) { for(j=0;j<m;j++) { scanf("%c",&map[i][j]); if(map[i][j]=='a') { s_x=i; s_y=j; } } getchar(); } bfs(); for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(map[i][j]=='r') { if(vis[i][j]==0) continue; else { if(ans>vis[i][j]) ans=vis[i][j]; } } } } if(ans==10000000) printf("Poor ANGEL has to stay in the prison all his life.\n"); else printf("%d\n",ans-1); } return 0; }