HDU 1242 Rescue(BFS或BFS+优先队列)

HDU 1242 Rescue(BFS或BFS+优先队列)

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

题意:有个R*C的迷宫,里面有一个a和多个r和多个x,现在你要从这多个r点走到a点去,且如果各自是x,则要花时间消灭守卫,即多花1分钟.问你从任意r点到a的最少时间是多少?

分析:

网上题解多说用优先队列,但是对于为什么用优先队列可以解,解释很少.

现在假设我们从多个r源点往a走,我们不能走已经被别人走过的或自己之前走过的格子.这句话的意思是说:如果有任意一个人走到(1,1)格子上花了1分钟,那么如果你再次走到(1,1)格子上花了>=1分钟的时间,你当前状态可以抛弃,因为后面你无论怎么走你也不可能快过之前走的人.

可能你会想如果之前的人因为消灭守卫花了时间,我是不是能超过他?不可能的,因为如果你在他消灭守卫之前赶上他,你也要消灭守卫.如果之后追到他(假设守卫被他消灭,你已经不用消灭了),你也最多是和他同样的状态.所以你这个目前状态是可以被抛弃的.

此题可以用优先队列+BFS来做,也可以不用优先队列,只用BFS做,就像我前面做过的一题一样,不过忘了哪题了.

不用优先队列的话,要用dist[r][c]来表示到达(r,c)点的最少时间,如果当前状态时间>=dist[r][c]直接抛弃即可.

AC代码:未用优先队列,93ms.

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200+5;
int dr[]={-1,1,0,0};
int dc[]={0,0,-1,1};
int R,C;
char map[maxn][maxn];
int dist[maxn][maxn];//最小时间
struct Node
{
    int r,c,d;//d表示时间
    Node(){}
    Node(int r,int c,int d):r(r),c(c),d(d){}
};
Node s[maxn*maxn];
int cnt;
int er,ec;
int BFS()
{
    queue<Node> Q;
    memset(dist,-1,sizeof(dist));
    for(int i=0;i<cnt;i++)
    {
        Q.push(s[i]);
        dist[s[i].r][s[i].c]=0;
    }
    while(!Q.empty())
    {
        Node node=Q.front(); Q.pop();
        int r=node.r, c=node.c;
        for(int d=0;d<4;d++)
        {
            int nr=r+dr[d], nc=c+dc[d];
            if(nr<0||nr>=R||nc<0||nc>=C||map[nr][nc]=='#') continue;
            int ndist = map[nr][nc]=='x'? node.d+2:node.d+1;
            if(dist[nr][nc]==-1||dist[nr][nc]>ndist)
            {
                dist[nr][nc]=ndist;
                Q.push(Node(nr,nc,ndist));
            }
        }
    }
    return dist[er][ec];
}
int main()
{
    while(scanf("%d%d",&R,&C)==2)
    {
        cnt=0;
        for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
        {
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='r')
            {
                s[cnt++]=Node(i,j,0);
                map[i][j]='.';
            }
            else if(map[i][j]=='a')
            {
                er=i,ec=j;
            }
        }
        int ans=BFS();
        if(ans==-1) printf("Poor ANGEL has to stay in the prison all his life.\n");
        else printf("%d\n",ans);
    }
    return 0;
}