`
bcyy
  • 浏览: 1810131 次
文章分类
社区版块
存档分类
最新评论

hdu 1242 优先队列广搜

 
阅读更多

http://acm.hdu.edu.cn/showproblem.php?pid=1242

该题可能有多个r点,但只有一个a点,所以从a开始搜索。因为道路上有两种情况,当步数相同时所耗时间可能不同,而最后要求最短时间,所以应按时间小优先而不是步数少优先。

#include<stdio.h>
#include<queue>
#define N 202
using namespace std;
int flag[N][N],n,m,x,y,i,j,ans;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
struct node
{
    friend bool operator<(node a,node b)
    {
        return a.time>b.time;
    }
    int x,y,time;
};
int BFS(int a,int b)
{
    priority_queue<node>q;
    node now,next;
    now.x=x;now.y=y;now.time=0;
    q.push(now);
    while(!q.empty())
    {
        now=q.top();
        q.pop();
        for(i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            next.time=now.time+1;
            if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&flag[next.x][next.y]!=0)
            {
                if(flag[next.x][next.y]==3)
                    return next.time;
                if(flag[next.x][next.y]==2)
                    next.time++;
                flag[next.x][next.y]=0;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    char t;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            getchar();
            for(j=0;j<m;j++)
            {
                scanf("%c",&t);
                if(t=='#')
                    flag[i][j]=0;
                if(t=='.')
                    flag[i][j]=1;
                if(t=='x')
                    flag[i][j]=2;
                if(t=='r')
                    flag[i][j]=3;
                if(t=='a')
                {
                    x=i;
                    y=j;
                }
            }
        }
        ans=BFS(x,y);
        if(ans!=-1)
            printf("%d\n",ans);
        else
            printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics