﻿ hdu 2612(Find a way)(简单广搜)

# Find a way

### Problem Description

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.

### Input

The 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.
‘@’ KCF

### Output

For 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.

```4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
```

### Sample Output

```66
88
66```
```#include <iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<algorithm>
using namespace std;
int dr={{1,0},{0,1},{-1,0},{0,-1} };
int n,m,i,j,num,x1,x2,y1,y2,ans;
int vis,a;
char mp;
struct node
{
int x,y,ti;
};
deque<node> s;
void bfs(int x,int y)
{
int t=num;
node p;
p.x=x;
p.y=y;
p.ti=0;
s.clear();
s.push_back(p);
vis[x][y]=1;
while(!s.empty())
{
node q=s.front();
for(i=0;i<4;i++)
{
int xx=q.x+dr[i];
int yy=q.y+dr[i];
if(xx>=0 && xx<n && yy>=0 && yy<m && mp[xx][yy]!='#')
if (!vis[xx][yy])
{
p.x=xx;
p.y=yy;
p.ti=q.ti+1;
s.push_back(p);
vis[xx][yy]=1;
if(mp[xx][yy]=='@')
{
a[xx][yy]+=p.ti;
ans=min(ans,a[xx][yy]);
t--;
}
if(t==0) return;
}
}
s.pop_front();
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<n;i++)
{
scanf("%s",&mp[i]);
for(j=0;j<m;j++)
if (mp[i][j]=='Y') x1=i,y1=j;
else if(mp[i][j]=='M') x2=i,y2=j;
else if (mp[i][j]=='@') {num++; a[i][j]=0;}
}
memset(vis,0,sizeof(vis));
bfs(x1,y1);
ans=1000000;
memset(vis,0,sizeof(vis));
bfs(x2,y2);
printf("%d\n",ans*11);
}
return 0;
}```