hdu2612.。。。

水了一天bfs了

题意：2个人分别从Y，M出发，到达其中任意一个“@” （图中有多个“@”点），2人到达的必须是同一个“@”点，求最短的路程和

思路：bfs搜2次，用一个2维数组记录到达各个“@”的距离之和再遍历求最小的（用一个数组就可以的原因是Y可以到达的地方M一定也能到达，因为Y，M必然可以相遇，所以Y和M必然是连通，一开始还怀疑了一下自己）

#include "map"

#include "queue"

#include "math.h"

#include "stdio.h"

#include "string.h"

#include "iostream"

#include "algorithm"

19:01:0019:01:162016-08-05#define abs(x) x > 0 ? x : -x

#define max(a,b) a > b ? a : b

#define min(a,b) a < b ? a : b

using namespace std;

int d[][] = {{,},{,},{,-},{-,}};

int Map[][],l[][];

bool vis[][];

struct Node

{

    int xx,yy;

    int step;

};

void Bfs(int x,int y)

{

    memset(vis,,sizeof(vis));

    Node now,next;

    queue<Node>Q;

    now.xx = x;

    now.yy = y;

    now.step = ;

    vis[x][y] = ;

    Q.push(now);

    while(!Q.empty())

    {

        now = Q.front();

        Q.pop();

        if(Map[now.xx][now.yy]==)

            l[now.xx][now.yy] += now.step;

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

        {

            next.xx = now.xx + d[i][];

            next.yy = now.yy + d[i][];

            next.step = now.step + ;

            if(Map[next.xx][next.yy]!= && !vis[next.xx][next.yy])

            {

                vis[next.xx][next.yy] = ;

                Q.push(next);

            }

        }

    }

}

int main()

{

    int x1,y1,x2,y2,n,m,ans,i,j;

    char c;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(Map,,sizeof(Map));

        memset(l,,sizeof(l));

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

        {

            getchar();

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

            {

                scanf("%c",&c);

                if(c=='.')

                    Map[i][j] = ;

                if(c=='#')

                    Map[i][j] = ;

                if(c=='Y')

                {

                    Map[i][j] = ;

                    x1 = i,y1 = j;

                }

                if(c=='M')

                {

                    Map[i][j] = ;

                    x2 = i,y2 = j;

                }

                if(c=='@')

                    Map[i][j] = ;

            }

        }

        Bfs(x1,y1);

        Bfs(x2,y2);

        ans = ;

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

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

            {

                if(l[i][j]!=)

                ans = min(ans,l[i][j]);

            }

        printf("%d\n",ans*);

    }

    return ;

}

巴特西

hdu2612.。。。

最新文章

热门文章