(简单) HDU 2612 Find a way，BFS。

　　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.

　　就是求两个人到某一个KFC的最小值，这个题记得以前做的时候被坑惨了，要注意初始化为INF，以及说人的起始位置要表示为可通过。

代码如下：

#include<iostream>

#include<cstring>

using namespace std;

const int INF=1e7;

short map1[][];

int que[],las,fir;

int ans[][];

int ans1[][];

int N,M;

int couKFC,Si,Sj,Ei,Ej;

bool judge(int x,int y,int (*rem)[])

{

    if(x<=||y<=||x>N||y>M)

        return ;

    if(rem[x][y]!=INF)

        return ;

    if(map1[x][y]==)

        return ;

    return ;

}

void bfs(int x,int y,int (*rem)[])

{

    las=fir=;

    int cou=;

    int temp,t1,t2;

    que[las++]=x*+y;

    rem[x][y]=;

    while(las-fir)

    {

        temp=que[fir++];

        t1=temp/;

        t2=temp%;

        temp=rem[t1][t2];

        if(map1[t1][t2]==)

            ++cou;

        if(cou>=couKFC)

            return;

        --t1;

        if(judge(t1,t2,rem))

        {

            rem[t1][t2]=temp+;

            que[las++]=t1*+t2;

        }

        t1+=;

        if(judge(t1,t2,rem))

        {

            rem[t1][t2]=temp+;

            que[las++]=t1*+t2;

        }

        --t1;

        --t2;

        if(judge(t1,t2,rem))

        {

            rem[t1][t2]=temp+;

            que[las++]=t1*+t2;

        }

        t2+=;

        if(judge(t1,t2,rem))

        {

            rem[t1][t2]=temp+;

            que[las++]=t1*+t2;

        }

    }

}

int slove()

{

    bfs(Si,Sj,ans);

    bfs(Ei,Ej,ans1);

    int minn=INF;

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

        for(int j=;j<=M;++j)

            if(map1[i][j]==)

                if(minn>ans[i][j]+ans1[i][j])

                    minn=ans[i][j]+ans1[i][j];

    return minn*;

}

int main()

{

    ios::sync_with_stdio(false);

    char c;

    while(cin>>N>>M)

    {

        couKFC=;

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

            for(int j=;j<=M;++j)

            {

                cin>>c;

                ans[i][j]=ans1[i][j]=INF;

                switch(c)

                {

                    case 'Y':

                        map1[i][j]=;

                        Si=i;

                        Sj=j;

                        break;

                    case 'M':

                        map1[i][j]=;

                        Ei=i;

                        Ej=j;

                        break;

                    case '.':

                        map1[i][j]=;

                        break;

                    case '#':

                        map1[i][j]=;

                        break;

                    case '@':

                        map1[i][j]=;

                        ++couKFC;

                        break;

                }

            }

        cout<<slove()<<endl;

    }

    return ;

}

巴特西

(简单) HDU 2612 Find a way，BFS。

最新文章

热门文章