ZOJ 3652 Maze 模拟,bfs,读题 难度:2

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

要注意题目中两点:

1.在踏入妖怪控制的区域那一刹那,先减行动力,然后才能杀妖怪

2.在妖怪控制区域行动力也会恢复

3.妖怪也许不在自己的控制区域

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn=100;

const int dx[4] = {0,0,-1,1};

const int dy[4] = {1,-1,0,0};

int n,m,l,k,sx,sy,tx,ty;

int maz[maxn][maxn];

int mon[6][2];

int vis[maxn][maxn][maxn];

int ind[maxn][maxn];

struct P{

    int x,y,sta,r;

    P(){x = y = sta = r = 0;}

    P(int _x,int _y,int _sta,int _r){

        x = _x;

        y = _y;

        sta = _sta;

        r = _r;

    }

    bool operator <(P p2)const {

        if(vis[x][y][sta] != vis[p2.x][p2.y][p2.sta])

            return vis[x][y][sta] > vis[p2.x][p2.y][p2.sta];

        return r < p2.r;

    }

};

int ok(int x,int y,int sta){

    if(x < 1 || y < 1 || x > n || y > m)return -1;

    int ki = maz[x][y];

    if(ki == -1)return -1;

    if(ki > 0){

        if(sta & (1 << (ki-1)))return 1;

        return 0;

    }

    return 1;

}

priority_queue <P> que;

int bfs(){

    memset(vis ,-1, sizeof vis);

    vis[sx][sy][0] = 0;

    que.push(P(sx,sy,0,0));

    while(!que.empty()){

        P tp=que.top();que.pop();

       // printf("pop  x: %d y: %d sta: %d step %d turn %d\n",tp.x,tp.y,tp.sta,tp.r,vis[tp.x][tp.y][tp.sta]);

        if(tx == tp.x && ty == tp.y)return vis[tx][ty][tp.sta];

        for(int i = 0;i < 4;i++){

            int tmpx = tp.x + dx[i];

            int tmpy = tp.y + dy[i];

            int sta = tp.sta;

            if(ind[tmpx][tmpy] != 0)sta |= (1 << (ind[tmpx][tmpy] - 1));

            if(ok(tmpx,tmpy,tp.sta) >= 0 && vis[tmpx][tmpy][sta] == -1){

                if(tp.r == 0){

                    vis[tmpx][tmpy][sta] = vis[tp.x][tp.y][tp.sta] + 1;

                   // printf("push x: %d y: %d sta: %d step %d turn %d\n",

                    //       tmpx,tmpy,sta,(ok(tmpx,tmpy,sta)==0?0:l-1),vis[tp.x][tp.y][tp.sta]+1);

                    que.push(P(tmpx,tmpy,sta,(ok(tmpx,tmpy,tp.sta) == 0?0:l-1)));

                }

                else {

                    vis[tmpx][tmpy][sta] = vis[tp.x][tp.y][tp.sta];

                    //printf("push x: %d y: %d sta: %d step %d turn %d\n",

                      //     tmpx,tmpy,sta,(ok(tmpx,tmpy,sta)==0?0:tp.r-1),vis[tp.x][tp.y][tp.sta]);

                    que.push(P(tmpx,tmpy,sta,(ok(tmpx,tmpy,tp.sta) == 0?0:tp.r-1)));

                }

            }

        }

    }

    return -1;

}

int main(){

    while(scanf("%d%d%d",&n,&m,&l) == 3){

        while(!que.empty())que.pop();

        memset(ind,0,sizeof ind);

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

            for(int j = 1;j <= m;j++){

                scanf("%d",maz[i]+j);

            }

        }

        scanf("%d",&k);

        for(int i = 1;i <= k;i++){

            scanf("%d%d",mon[i],mon[i] + 1);

            ind[mon[i][0]][mon[i][1]]=i;

        }

        scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

        int ans = bfs();

        if(ans < 0){

            puts("We need God's help!");

        }

        else {

            printf("%d\n",ans);

        }

    }

    return 0;

}