N

这个专题的最后一道题目了....

应该说的是有两个人计划去KFC碰头，找出来一个最近的KFC让他们俩见面吧，应该是个比较容易的问题，不过需要注意在一个Bfs里面搜的话，别把两个人弄混乱了...........................可以在定义的时候使用一个简单的数组标记，我还是是用一个简单的三维数组标记吧，注意求的是两个人在路上用的总时间

////////////////////////////////////////////////

 #include<algorithm>

#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;

const int maxn = 205;
const int oo = 0xfffffff;

struct node{int x, y, op;};//op等于0的时候代表是Y，1代表M
char G[maxn][maxn];
int v[maxn][maxn][2];
int M, N;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

int Bfs(node s, node q)
{
    queue<node> Q;
    int Min = oo;
    Q.push(s), Q.push(q);
    v[s.x][s.y][s.op] = v[q.x][q.y][q.op] = 1;

    while(Q.size())
    {
        s = Q.front();Q.pop();

        if(G[s.x][s.y] == '@' && v[s.x][s.y][0] && v[s.x][s.y][1])
            Min = min(Min, v[s.x][s.y][0]+v[s.x][s.y][1]);

        for(int i=0; i<4; i++)
        {
            q = s;
            q.x += dir[i][0], q.y += dir[i][1];

            if(q.x>=0&&q.x<M && q.y>=0&&q.y<N && G[q.x][q.y] != '#' && v[q.x][q.y][q.op]==0)
            {
                v[q.x][q.y][q.op] = v[s.x][s.y][s.op] + 1;
                Q.push(q);
            }
        }
    }

    return Min-2;
}

int main()
{
    while(scanf("%d%d", &M, &N) != EOF)
    {
        node s, q;
        int i, j;

        for(i=0; i<M; i++)
        {
            scanf("%s", G[i]);
            for(j=0; j<N; j++)
            {
                if(G[i][j] == 'Y')
                    s.x = i, s.y = j, s.op=0;
                if(G[i][j] == 'M')
                    q.x = i, q.y = j, q.op=1;
            }
        }

        memset(v, 0, sizeof(v));

        int ans = Bfs(s, q);

        printf("%d
", ans*11);
    }

    return 0;
}