4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...#
66 88 66
题意，Y和M两个人分别同乡村和城市出发，想去吃KFC，问最短时间能到达哪家KFC。
注意：Y走的话，可以走M。M走的话，可以走Y。‘@’代表KFC。‘#’是不能走的。
思路：跑两遍BFS，将每个人到达每一个KFC的步数用数组记录下来，然后遍历整个地图，找到两个人同时到达某一个KFC的最小值。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#define inf 0x6ffffff
using namespace std;
char map[202][202];// 地图
int vis[202][202];// 标记数组
int flag1[202][202];//记录M到达任意KFC的时间
int flag[202][202];//记录Y到达任意KFC的时间
int n,m;
int x1,y1,x2,y2;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct node
{
int x,y,step;
}
;
bool check(int x,int y)
{
if(x<0 ||y<0 ||x>=n ||y>=m ||map[x][y]=='#' ||vis[x][y]) //检查是否越界，是否已经搜过
return 0;
return 1;
}
void bfs(int x,int y,int a[][202]) //进入坐标和记录数组
{
int i;
node st,ed;
queue<node>q;
st.x=x;
st.y=y;
st.step=0;
q.push(st);
while(!q.empty())
{
st=q.front();
q.pop();
for(i=0;i<4;i++)
{
ed.x=st.x+dir[i][0];
ed.y=st.y+dir[i][1];
if(!check(ed.x,ed.y))
continue;
ed.step=st.step+1;
vis[ed.x][ed.y]=1;
if(map[ed.x][ed.y]=='@')
{
a[ed.x][ed.y]=ed.step;
}
q.push(ed);
}
}
}
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
memset(flag,0,sizeof(flag));
memset(vis,0,sizeof(vis));
memset(flag1,0,sizeof(flag1));//全部初始化
for(i=0;i<n;i++)
scanf("%s",map[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(map[i][j]=='Y')
{
x1=i;
y1=j;
}
if(map[i][j]=='M')
{
x2=i;
y2=j;
}
}
vis[x1][y1]=1;
bfs(x1,y1,flag);//一遍BFS之后
memset(vis,0,sizeof(vis));//初始化
vis[x2][y2]=1;
bfs(x2,y2,flag1); //再跑一遍BFS。
int min=inf;
for(i=0;i<n;i++)
for(j=0;j<m;j++) //遍历整个地图、
{
if(min>flag[i][j]+flag1[i][j] &&flag[i][j] &&flag1[i][j])//有值的地方说明有KFC，找出两个人同时到达一个KFC的最短时间
min=flag[i][j]+flag1[i][j];
}
printf("%d\n",min*11);//每走一步为11分钟。
}
return 0;
}
原文：http://blog.csdn.net/sky_miange/article/details/43561785