D - Find a way

        Find a way这题目要多坑有多坑,竟然会有KFC四周全是墙的这种测试数据,你家开个KFC旁边全都建个墙围起来?

好吧,吐槽完毕,说下解题思路,一开始我是从每个KFC向Y、M使用BFS来找最短路径,把每个KFC到他们两个人的最短路径放到列队里面去,最后front()出来计算最小的,但是,很不幸,这样会Time Limit Exceeded,所以,改一下,建两张标记地图,把kfc放到queue里面去,把每个KFC到Y、M的最短步数搜出来,分别放到另外两个队列里面去,最后从另外两个队列里面front()出来,计算最小的那个。


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. 
‘#’ 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.
 

Sample Input

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

Sample Output

66
88
66



下面贴出代码,仅供参考:


#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
class Point//实例化一个位置类
{
public:
    int x;
    int y;
    int step;
    Point(int px, int py, int ps):x(px),y(py),step(ps){}
};
const int maxn = 200+10;
char omap[maxn][maxn];
bool flag[maxn][maxn];
int n, m;
queue<Point> kfcqueue;
queue<int> yqueue;
queue<int> mqueue;
void Init()
{
    //读入地图数据,把KFC读入列队
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    {
        cin>>omap[i][j];
        if(omap[i][j]=='@')
        {
            Point kfc(i, j, 0);
            kfcqueue.push(kfc);
        }
    }
}
bool check(int ix, int iy)//检查是否可以走的函数
{
    return (ix<=0||ix>n||iy<=0||iy>m||omap[ix][iy]=='#'||flag[ix][iy]==true)?false:true;
}
void Bfs(int yx, int yy, int ystep, char ch)//BFS我就不多说什么了,都是模板,都是套路
{
    queue<Point> myqueue;
    //这里一定要记得清空标记数组,因为只有一个标记地图
    memset(flag, 0, sizeof(flag));
    Point beginPoint(yx, yy, ystep), next(0, 0, 0);
    flag[yx][yy]=true;
    myqueue.push(beginPoint);
    while(!myqueue.empty())
    {
        beginPoint = myqueue.front();
        myqueue.pop();
        if(omap[beginPoint.x][beginPoint.y]==ch)
        {
            if(ch=='Y'){yqueue.push(beginPoint.step);break;}
            if(ch=='M'){mqueue.push(beginPoint.step);break;}
        }
        for(int fx=1;fx<=4;fx++)
        {
            
            if(fx==1){next=beginPoint;next.y=beginPoint.y-1;}//向上搜索
            if(fx==2){next=beginPoint;next.y=beginPoint.y+1;}//向下搜索
            if(fx==3){next=beginPoint;next.x=beginPoint.x-1;}//向左搜索
            if(fx==4){next=beginPoint;next.x=beginPoint.x+1;}//向右搜索
            if(check(next.x, next.y))
            {
                next.step = beginPoint.step+1;
                flag[next.x][next.y]=true;
                myqueue.push(next);
            }
        }
    }
}
void Process()
{
    while(!kfcqueue.empty())
    {
        Point kfc_begin=kfcqueue.front();
        kfcqueue.pop();
        Bfs(kfc_begin.x, kfc_begin.y, kfc_begin.step, 'Y');
        Bfs(kfc_begin.x, kfc_begin.y, kfc_begin.step, 'M');
    }
}
void Print()
{
    int ans, add;
    while(!yqueue.empty()||!mqueue.empty())
    {
        add = yqueue.front()+mqueue.front();
        //cout<<add<<endl;
        yqueue.pop();
        mqueue.pop();
        ans = ans>(add)?add:ans;
    }
    cout<<ans*11<<endl;
}
void TestCase()
{
    //地图数据读入测试
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)cout<<omap[i][j];
        cout<<endl;
    }
}
int main()
{
    while(cin>>n>>m)
    {
        Init();
        //TestCase();
        Process();
        Print();
    }
    return 0;
}