Find a way

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.

Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.

InputThe input contains multiple test cases.

Each test case include, first two integers n, m. (2<=n,m<=200).

Next n lines, each line included m character.

‘Y’ express yifenfei initial position.

‘M’ express Merceki initial position.

‘#’ forbid road;

‘.’ Road.

‘@’ KCF

OutputFor each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.Sample Input

4 4

Y.#@

....

.#..

@..M

4 4

Y.#@

....

.#..

@#.M

5 5

Y..@.

.#...

.#...

@..M.

#...#

Sample Output

66

88

66

主要思想：不能直接用枚举，这样容易超时（不信可以试试）。用bfs把每一个位置遍历，发现@就记录一下。其中也有一些问题，比如怎么对每一个@进行区别，和如果有一个@两个人都不能到达或者有一个人不能到达怎么办（这个需要读题仔细）。
解决方法：用二维数组，对@位置进行记录，再用一个一维数组判断是不是两个人都到了。

#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 10000
using namespace std;
typedef pair<int,int> ee;
bool vis[209][209];
int t[4][2]={0,1,1,0,-1,0,0,-1};
int d[209][209];
char a[209][209];
int b[1009][1009];
int g[1009][1009];
queue<ee> que;
int n,m,k;
int tx,ty,sx,sy,mx,my;

void clean()
{
while(!que.empty()) que.pop();
return;
}

void bfs(int x,int y)
{
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
d[x][y]=0;
que.push(ee(x,y));
vis[x][y]=true;

while(!que.empty())
{
ee exa=que.front();
que.pop();
if(a[exa.first][exa.second]=='@')
{
b[exa.first][exa.second]=b[exa.first][exa.second]+d[exa.first][exa.second];
g[exa.first][exa.second]++;
}
for(int i=0;i<4;i++)
{
tx=exa.first+t[i][0];
ty=exa.second+t[i][1];

if(tx<1||ty<1||tx>n||ty>m) continue;
if(a[tx][ty]=='#') continue;
if(vis[tx][ty]) continue;

que.push(ee(tx,ty));
vis[tx][ty]=true;
d[tx][ty]=d[exa.first][exa.second]+1;
// printf("%d\n",d[tx][ty]);
}
}
clean();
return;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
k=0;
memset(b,INF,sizeof(b));
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
for(int j=1;j<=m;j++)
{
if(a[i][j]=='Y'){sx=i;sy=j;}
if(a[i][j]=='M'){mx=i;my=j;}
if(a[i][j]=='@'){b[i][j]=0;}
}
}
bfs(sx,sy);
bfs(mx,my);
int x1=1,x2=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(b[i][j]<b[x1][x2]&&g[i][j]==2)
{
b[x1][x2]=b[i][j];
}
}
}
printf("%d\n",b[x1][x2]*11);
}

return 0;
}