题目链接：hdu2612

思路：题意是求两个人到某一个KFC花费时间和最小，其实就是求最短距离和，用两个BFS，分别以两个人为起点，分别记录下两人到每个KFC的距离，然后求出最小的和

#include<stdio.h>

#include<string.h>

#include<queue>

#include<algorithm>

#define N 205

using namespace std;

char map[N][N];

int v[N][N],ans1[N][N],ans2[N][N],d[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

int x1,x2,y1,y2,n,m,num;

struct node

{

    int x,y,step;

    friend bool operator < (node a,node b)

    {

        return a.step > b.step;

    }

};

void bfs1(int x,int y,int total)//total表示KFC的总数目

{

    memset(ans1,1,sizeof(ans1));

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

    priority_queue <node> q;

    node s,temp;

    s.x = x;

    s.y = y;

    s.step = 0;

    v[x][y] = 1;

    q.push(s);

    while(!q.empty())

    {

        temp = q.top();

        q.pop();

        if(map[temp.x][temp.y] == '@')

        {

            ans1[temp.x][temp.y] = temp.step;

            total -- ;

        }

        if(total == 0) return;//所有的KFC都已经计算过

        for(int i= 0 ; i < 4 ; i ++)

        {

            s = temp;

            s.x += d[i][0];

            s.y += d[i][1];

            if(s.x < 0 || s.x >= n || s.y < 0 || s.y >= m || v[s.x][s.y] || map[s.x][s.y] == '#')

             continue;

            v[s.x][s.y] = 1;

            s.step ++;

            q.push(s);

        }

    }

}

void bfs2(int x,int y,int total)

{

    memset(ans2,1,sizeof(ans2));

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

    priority_queue <node> q;

    node s,temp;

    s.x = x;

    s.y = y;

    s.step = 0;

    v[x][y] = 1;

    q.push(s);

    while(!q.empty())

    {

        temp = q.top();

        q.pop();

        if(map[temp.x][temp.y] == '@')

        {

            ans2[temp.x][temp.y] = temp.step;

            total -- ;

        }

        if(total == 0) return;

        for(int i= 0 ; i < 4 ; i ++)

        {

            s = temp;

            s.x += d[i][0];

            s.y += d[i][1];

            if(s.x < 0 || s.x >= n || s.y < 0 || s.y >= m || v[s.x][s.y] || map[s.x][s.y] == '#')

             continue;

            v[s.x][s.y] = 1;

            s.step ++;

            q.push(s);

        }

    }

}

int main()

{

    int i,j;

    while(~scanf("%d%d",&n,&m))

    {

        num = 0;

        for(i = 0 ; i < n ; i ++)

        {

            scanf("%s",map[i]);

            for(j = 0 ; j < m ; j ++)

            {

                if(map[i][j] == 'Y')

                {

                    x1 = i;

                    y1 = j;

                }

                else if(map[i][j] == 'M')

                {

                    x2 = i;

                    y2 = j;

                }

                else if(map[i][j] == '@')

                 num++;

            }

        }

        bfs1(x1,y1,num);

        bfs2(x2,y2,num);

        int sum = 10000000;

        for(i = 0 ; i < n ; i ++)

        for(j = 0 ; j < m ; j ++)

        if(map[i][j] == '@')

        {

            sum = min(sum,ans1[i][j] + ans2[i][j]);

        }

        printf("%d\n",sum * 11);

    }

    return 0;

}