一个二维表:
.:路
#:障碍
a:要救的人
r:去找的人(有多个)
x:门卫
找人中若遇到门卫要多花一个单位的时间
本题可以反过来做,用a去找最近的r;
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<queue> 4 #include<string.h> 5 #include <iostream> 6 using namespace std; 7 char map[201][201]; 8 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 9 int visited[201][201]; 10 int co,ro; 11 struct coor 12 { 13 int x,y; 14 int step; 15 }; 16 queue<coor>que; 17 bool judge(int x,int y) 18 { 19 if(x<0||y<0||x>=co||y>=ro||map[x][y]=='#'||visited[x][y]) 20 return false; 21 return true; 22 } 23 bool bfs(int a,int b) 24 { 25 int x,y,i; 26 coor in,out; 27 memset(visited,0,sizeof(visited)); 28 while(!que.empty()) 29 que.pop(); 30 in.x=a; 31 in.y=b; 32 in.step=0; 33 que.push(in); 34 while(!que.empty()) 35 { 36 out=que.front(); 37 que.pop(); 38 if(map[out.x][out.y]=='r') 39 { 40 printf("%d\n",out.step); 41 return true; 42 } 43 for(i=0;i<4;i++) 44 { 45 x=out.x+dir[i][0]; 46 y=out.y+dir[i][1]; 47 if(!judge(x,y)) 48 continue; 49 visited[x][y]=1; 50 in.x=x; 51 in.y=y; 52 in.step=out.step+1; 53 if(map[x][y]=='x') 54 in.step++; 55 que.push(in); 56 } 57 } 58 return false; 59 } 60 61 int main() 62 { 63 int i,a,b,j; 64 while(scanf("%d%d",&co,&ro)!=EOF) 65 { 66 for(i=0;i<co;i++) 67 scanf("%s",map[i]); 68 for(i=0;i<co;i++) 69 for(j=0;j<co;j++) 70 if(map[i][j]=='a') 71 { 72 a=i; 73 b=j; 74 } 75 if(!bfs(a,b)) 76 printf("Poor ANGEL has to stay in the prison all his life.\n"); 77 } 78 return 0; 79 }