ZOJ 3652 MAZE(BFS)

转载请注明出处,谢谢http://www.voidcn.com/article/p-swwlcvya-bae.html       by---cxlove 

题目:给出一个迷宫,其中有k个怪物在某些位置,每个怪物控制着某些位置对于主人公造成伤害。

初始有一个移动力,每走一步,移动力-1,如果进入到怪物控制的位置,而且怪物没有被消灭,则移动力减为0,进入下一轮,如果怪物消灭,则怪物所控制的所有区域视为空地,问最少需要多少轮到达目标位置

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

其实是个很无聊的BFS题。

题意 也很无聊。

其中有几点需要注意,如果起点与终点重合,答案是0,并没有开始第一轮

如果到达某个位置,是终点,但是移动为0,也无所谓,所以是先判有没有结束,再进入下一轮

即使某个位置为空地,也可以有怪物,被1号怪物控制的区域也可以是2号怪物,做的时候有点晕了。。。

4维判重,x坐标,y坐标,当前的移动力值,以及消灭怪物的情况(状态压缩)

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<28
#define M 6000005
#define N 205
#define maxn 300005
#define eps 1e-8
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
using namespace std;
int n,m,l,maze[55][55];
struct Node
{
    int x,y,hp,step,state;
    Node(){}
    bool check()
    {
        if(x>0&&x<=n&&y>0&&y<=m) return true;
        return false;
    }
    //优先队列
    bool operator<(const Node n1)const
    {
        return n1.step!=step?step>n1.step:hp<n1.hp;
    }
}s,e,pre,cur;
int way[4][2]={0,1,0,-1,1,0,-1,0},k;
bool flag[55][55][11][1<<5];
int mon[55][55];
void bfs()
{
    //这一步直接先判断掉
    if(s.x==e.x&&s.y==e.y)
    {
        printf("0\n");
        return;
    }
    mem(flag,false);
    s.hp=l;s.step=1;s.state=0;
    priority_queue<Node>que;
    while(!que.empty()) que.pop();
    flag[s.x][s.y][l][0]=true;
    que.push(s);
    while(!que.empty())
    {
        pre=que.top();
        que.pop();
        //注意当hp为0时,也可以结束,到达终点
        //所以是先判断到达终点, 然后再进入下一轮
        if(pre.x==e.x&&pre.y==e.y)
        {
            printf("%d\n",pre.step);
            return;
        }
        //移动为0,则下一轮
        if(pre.hp==0)
        {
            pre.step++;
            pre.hp=l;
            if(!flag[pre.x][pre.y][pre.hp][pre.state])
            {
                flag[pre.x][pre.y][pre.hp][pre.state]=true;
                que.push(pre);
            }
            continue;
        }
        for(int i=0;i<4;i++)
        {
            cur=pre;
            cur.x+=way[i][0];
            cur.y+=way[i][1];
            if(!cur.check()||maze[cur.x][cur.y]<0) continue;
            if(maze[cur.x][cur.y]==0||((1<<(maze[cur.x][cur.y]-1))&cur.state))
            {
                //当前为空地,也可以有怪,消灭
                if(mon[cur.x][cur.y]>=0)
                    cur.state|=(1<<mon[cur.x][cur.y]);
                cur.hp--;
            }
            else
            {
                if(mon[cur.x][cur.y]>=0)
                    cur.state|=(1<<mon[cur.x][cur.y]);
                cur.hp=0;

            }
            if(!flag[cur.x][cur.y][cur.hp][cur.state])
            {
                flag[cur.x][cur.y][cur.hp][cur.state]=true;
                que.push(cur);
            }
        }
    }
    puts("We need God's help!");
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&l)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&maze[i][j]);
            }
        }
        scanf("%d",&k);
        mem(mon,-1);
        for(int i=0;i<k;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            mon[x][y]=i;
        }
        scanf("%d%d%d%d",&s.x,&s.y,&e.x,&e.y);
        bfs();
    }
    return 0;
}
相关文章
相关标签/搜索