HDU 1242 && ZOJ 1649( BFS (队列 || 优先队列)).

51 阅读 0 评论 34 点赞

我是靠谱客的博主小巧小蝴蝶，最近开发中收集的这篇文章主要介绍HDU 1242 && ZOJ 1649( BFS (队列 || 优先队列)).，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

~~~~

突然发现一篇搜索的题目都有写。昨天发现道bfs题目，HDU上AC, ZOJ上WA。不得不说HDU上的数据之水。。

今天早起刷题有了思路，并用队列和单调队列都写了一遍，0MS飘过~~

~~~~

题目链接：

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

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=649

~~~~

首先有坑的地方是friends，对嘛，朋友有很多，angel只有一个。所以更好的处理办法就是以angel为起点。

其次是杀死guard并走到其位置上需要2mins，这样就违背了BFS等距离向外扩展的原理（应该是这样说吧，大牛请卖萌）。

所以用队列的话，可以把杀死guard和走到其位置上看成两个步骤，入队两次。

优先队列就简单了，直接以时间从小到大建立优先级就好了。

~~~~

队列：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define N 222
using namespace std;

int n,m;
char g[N][N];
int dir[4][2]={1,0,-1,0,0,-1,0,1};
struct node
{
    int x,y;
    int t;
};
int bfs(int x,int y)
{
    queue<node> q;
    node cur,next;
    cur.x=x,cur.y=y,cur.t=0;
    q.push(cur);
    g[x][y]='#';    //相当于vis数组记录是否访问过。
    while(!q.empty())
    {
        cur=q.front();
        q.pop();
        if(g[cur.x][cur.y]=='y')
        {
            g[cur.x][cur.y]='#'; //~~
            cur.t=cur.t+1;
            q.push(cur);    //再入队一次
            continue;
        }
        for(int i=0;i<4;i++)
        {
            next.x=cur.x+dir[i][0],next.y=cur.y+dir[i][1];
            if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && g[next.x][next.y]!='#')
            {
                if(g[next.x][next.y]=='.')
                {
                    g[next.x][next.y]='#';
                    next.t=cur.t+1;
                    q.push(next);
                }
                else if(g[next.x][next.y]=='x') //~~
                {
                    g[next.x][next.y]='y';  //~~
                    next.t=cur.t+1;
                    q.push(next);
                }
                else if(g[next.x][next.y]=='r')
                    return cur.t+1;
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int sx,sy;
        for(int i=0;i<n;i++)
        {
            scanf("%s",g[i]);
            for(int j=0;j<m;j++)
                if(g[i][j]=='a') sx=i,sy=j;
        }
        int t=bfs(sx,sy);
        if(t<0) puts("Poor ANGEL has to stay in the prison all his life.");
        else printf("%dn",t);
    }
    return 0;
}

优先队列：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define N 222
using namespace std;

int n,m;
char g[N][N];
int dir[4][2]={1,0,-1,0,0,-1,0,1};
struct node
{
    int x,y;
    int t;
};
bool operator < (node a,node b) 
{
    return a.t>b.t;  //~~
}
int bfs(int x,int y)
{
    priority_queue<node> q;
    node cur,next;
    cur.x=x,cur.y=y,cur.t=0;
    q.push(cur);
    g[x][y]='#';
    while(!q.empty())
    {
        cur=q.top();
        q.pop();
        for(int i=0;i<4;i++)
        {
            next.x=cur.x+dir[i][0],next.y=cur.y+dir[i][1];
            if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && g[next.x][next.y]!='#')
            {
                if(g[next.x][next.y]=='.')
                {
                    g[next.x][next.y]='#';
                    next.t=cur.t+1;
                    q.push(next);
                }
                else if(g[next.x][next.y]=='x')
                {
                    g[next.x][next.y]='#';
                    next.t=cur.t+2;
                    q.push(next);
                }
                else if(g[next.x][next.y]=='r')
                    return cur.t+1;
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        int sx,sy;
        for(int i=0;i<n;i++)
        {
            scanf("%s",g[i]);
            for(int j=0;j<m;j++)
                if(g[i][j]=='a') sx=i,sy=j;
        }
        int t=bfs(sx,sy);
        if(t<0) puts("Poor ANGEL has to stay in the prison all his life.");
        else printf("%dn",t);
    }
    return 0;
}