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.

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.
‘#’ forbid road;
‘.’ Road.
‘@’ 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.

SampleInput

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

SampleOutput

66
88
66

思路：题目大意是两位小朋友，Y和M要在肯德基见面，让我们帮他们找一个他们到达总时间最短时间。我想的是用一个mao<pair,int>这样的来存肯德基的坐标和对应所到达的时间，所以需要两次bfs，详情看代码吧

#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
int n,m,ya,yb,ma,mb;
int dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};//上下左右 
char Map[210][210];//地图 
typedef pair<int,int> PII;
struct que
{
    int x,y,t;
    que(int xx,int yy,int tt):x(xx),y(yy),t(tt){}
};
struct stu//记录两个小朋友到每个能到达的肯德基所需时间 
{
    map<PII,int> kcf;
};
 
bool check(int x,int y,bool vis[][210])
{
    if(x<0||x>=n||y<0||y>=m) return false;//越界 
    if(vis[x][y]) return false;//已经去过 
    if(Map[x][y]=='#') return false;//墙 
    
    return true;
}
void bfs(int a,int b,bool vis[][210],stu &H)//这里要地址传递 
{
    queue<que> q;
    q.push(que(a,b,0));
    vis[a][b] = true;
    while(!q.empty())
    {
        que u = q.front();
        q.pop();
        
        for(int i=0;i<4;i++)
        {
            int xx = u.x+dx[i];
            int yy = u.y+dy[i];
            
            if(!check(xx,yy,vis)) continue;
            
            if(Map[xx][yy]=='@')//到达一个肯德基记录下来 
            {
                PII p;
                p.first = xx;
                p.second = yy;
                H.kcf[p] = u.t+11;
            }
            q.push(que(xx,yy,u.t+11));
            vis[xx][yy] = true;
        }
    }
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%s",Map[i]);
            for(int j=0;j<m;j++)
            {
                if(Map[i][j] == 'Y')//Y的起点 
                {
                    ya = i;
                    yb = j;
                }
                if(Map[i][j] == 'M')//M的起点 
                {
                    ma = i;
                    mb = j;
                }
            }
        }
        bool visy[210][210];//记录Y是否去过某地 
        bool vism[210][210];//记录M是否去过某地 
        memset(visy,false,sizeof(visy));
        memset(vism,false,sizeof(vism));//初始化 
        stu Y,M;//用来存储去能去的肯德基时间 
        
        bfs(ya,yb,visy,Y);
        bfs(ma,mb,vism,M);
        
        int mmin = 0x3f3f3f;
        map<PII,int>::iterator it = Y.kcf.begin();
        
        for(it = Y.kcf.begin();it!=Y.kcf.end();it++)//遍历Y的肯德基 
        {
            if(visy[it->first.first][it->first.second]&&vism[it->first.first][it->first.second])//如果这个肯德基两个人都可以到达 
            {
                int tt = Y.kcf[it->first]+M.kcf[it->first];//两个人到达这个肯德基所需总时间 
                if(tt<mmin) mmin = tt;
            }
        }
        cout<<mmin<<endl;
    }
    return 0;
}