HDU 1242 (BFS搜索+优先队列)

时间：2023-03-08 19:05:05

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1242

题目大意：多个起点到一个终点，普通点耗时1，特殊点耗时2，求到达终点的最少耗时。

解题思路：

如果没有特殊点，就是普通BFS。

由于特殊点的介入，所以BFS树的同一深度，各个点的值可能不同。所以使用优先队列，先取出值小的搜。

搜到的第一个符合条件的结果肯定是最小的，break。

注意有多个起点，所以先记录下所有起点，依次BFS找最小。

#include "cstdio"

#include "string"

#include "cstring"

#include "iostream"

#include "vector"

#include "queue"

using namespace std;

#define inf 1<<28

struct status

{

    int x,y,dep;

    status(int x,int y,int dep):x(x),y(y),dep(dep) {}

    bool operator < (const status &a) const

    {

        return dep>a.dep;

    }

};

int n,m,map[][],vis[][],dir[][]={-,,,,,-,,},ans;

void bfs(int x,int y)

{

    priority_queue<status> Q;

    Q.push(status(x,y,));

    vis[x][y]=true;

    bool flag=false;

    while(!Q.empty())

    {

        if(flag) break;

        status t=Q.top();Q.pop();

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

        {

            int X=t.x+dir[s][],Y=t.y+dir[s][];

            if(vis[X][Y]||X<||X>n||Y<||Y>n||!map[X][Y]) continue;

            vis[X][Y]=true;

            if(map[X][Y]==) {flag=true;ans=min(ans,t.dep+);};

            if(map[X][Y]==) Q.push(status(X,Y,t.dep+));

            else Q.push(status(X,Y,t.dep+));

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    ios::sync_with_stdio(false);

    string tt;

    while(cin>>n>>m&&n)

    {

        vector<status> f;

        ans=inf;

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

        {

            cin>>tt;

            for(int j=;j<tt.size();j++)

            {

                if(tt[j]=='#') map[i][j+]=;

                if(tt[j]=='.') map[i][j+]=;

                if(tt[j]=='a') map[i][j+]=;

                if(tt[j]=='x') map[i][j+]=;

                if(tt[j]=='r') {map[i][j+]=;f.push_back(status(i,j+,));}

            }

        }

        for(int i=;i<f.size();i++)

        {

            memset(vis,,sizeof(vis));

            bfs(f[i].x,f[i].y);

        }

        if(ans!=inf) cout<<ans<<endl;

        else cout<<"Poor ANGEL has to stay in the * all his life."<<endl;

    }

}
11869491 2014-10-14 14:50:56 Accepted 1242 31MS 612K 1861 B C++ Physcal

相关文章