题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2612

 

题目大意：

M和Y想要在KFC见面，现在让你去找到一个使两个人到同一个KFC总花费时间最小的地方，然后输出最小的花费时间 （花费时间 = 步数*11）

 

思路：

先对M跑一次BFS并且用一个数组记录它到不同KFC的时间

再对Y跑一次BFS并且用另一个数组记录它到不同KFC的时间

然后遍历这两个数组，找到它们到同一个KFC花费的最小时间

 

具体代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 #include <algorithm>
 5 #define inf 0x6ffffff
 6 using namespace std;
 7 char map[202][202];// 地图
 8 int vis[202][202];//  标记数组
 9 int flag1[202][202];//记录M到达任意KFC的时间
10 int flag[202][202];//记录Y到达任意KFC的时间
11 int n,m;
12 int x1,y1,x2,y2;
13 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
14 struct node
15 {
16     int x,y,step;
17 }
18 ;
19 bool check(int x,int y)
20 {
21     if(x<0 ||y<0 ||x>=n ||y>=m ||map[x][y]=='#' ||vis[x][y]) //检查是否越界，是否已经搜过
22         return 0;
23     return 1;
24 }
25 void bfs(int x,int y,int a[][202]) //进入坐标和记录数组
26 {
27     int i;
28     node st,ed;
29     queue<node>q;
30     st.x=x;
31     st.y=y;
32     st.step=0;
33     q.push(st);
34     while(!q.empty())
35     {
36         st=q.front();
37         q.pop();
38         for(i=0;i<4;i++)
39         {
40             ed.x=st.x+dir[i][0];
41             ed.y=st.y+dir[i][1];
42             if(!check(ed.x,ed.y))
43                 continue;
44             ed.step=st.step+1;
45             vis[ed.x][ed.y]=1;
46             if(map[ed.x][ed.y]=='@')
47             {
48                 a[ed.x][ed.y]=ed.step;
49             }
50             q.push(ed);
51         }
52     }
53 }
54 int main()
55 {
56     int i,j;
57     while(~scanf("%d%d",&n,&m))
58     {
59         memset(flag,0,sizeof(flag));
60         memset(vis,0,sizeof(vis));
61         memset(flag1,0,sizeof(flag1));//全部初始化
62         for(i=0;i<n;i++)
63             scanf("%s",map[i]);
64         for(i=0;i<n;i++)
65             for(j=0;j<m;j++)
66             {
67                 if(map[i][j]=='Y')
68                 {
69                     x1=i;
70                     y1=j;
71                 }
72                 if(map[i][j]=='M')
73                 {
74                     x2=i;
75                     y2=j;
76                 }
77             }
78             vis[x1][y1]=1;
79             bfs(x1,y1,flag);//一遍BFS之后
80             memset(vis,0,sizeof(vis));//初始化
81             vis[x2][y2]=1;
82             bfs(x2,y2,flag1);  //再跑一遍BFS。
83             int min=inf;
84             for(i=0;i<n;i++)
85                 for(j=0;j<m;j++) //遍历整个地图、
86                 {
87                     if(min>flag[i][j]+flag1[i][j] &&flag[i][j] &&flag1[i][j])//有值的地方说明有KFC，找出两个人同时到达一个KFC的最短时间
88                         min=flag[i][j]+flag1[i][j];
89                 }
90                 printf("%d\n",min*11);//每走一步为11分钟。
91     }
92     return 0;
93 }