首页 > 代码库 > hdu 2102 A计划 具体题解 (BFS+优先队列)

hdu 2102 A计划 具体题解 (BFS+优先队列)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102

 

这道题属于BFS+优先队列

 

開始看到四分之中的一个的AC率感觉有点吓人,后来一做感觉就是模板改了点东西而已,一遍就AC了,只是在主函数和全局变量里面都定义了n和m导致我白白浪费了debug的时间。

果然全局变量得小心用啊。

 

跟模板一样的,定义一个结构体,仅仅只是多加了个參数,就是迷宫的层数,我用0代表第一层。1代表第二层,这在数组里面会体现的。


struct node {
    int index;//层数
    int x,y;//坐标
    int time;
    friend bool operator <(const node &a,const node &b){
    //时间少的放在队列前面
        return a.time>b.time;
    }
};


我定义的那个map
char map[2][11][11];

map[层数][x][y]这种。

还有个can_go 函数检測当前点是否可走:


int can_go(int index,int x,int y){
   if(x<0||x>=n||y<0||y>=m||map[index][x][y]==‘*‘){
    return 0;
   }
   return 1;
}

 

我大概就讲一下跟模板题有啥不同吧。

 

这道题里面会遇到传送门’#’仅仅要遇到就把当前层格子标记为已经过vis[index][x][y]=1之后立刻飞到还有一层即可了,注意,若还有一层是墙那就挂了,说明这里不能走,直接continue换个方向继续。或者还有一层同一位置也是传送门’#’那也不行,也continue即可了


if(map[!next.index][next.x][next.y]==‘*‘||
<span style="white-space:pre">	</span>map[!next.index][next.x][next.y]==‘#‘){
<span style="white-space:pre">	</span>continue;
}

之后仅仅要队列不为空。就取出队列的头节点,推断是否为终点,假设是,则返回到达当前节点所需时间即:now.time;若不是,那接下来把now的四个方向所有遍历一遍。假设遍历到达不是墙就将其增加队列。而且把当前time更新:next.time=now.time+1。一直循环直到que.top出来的坐标代表的是终点为止。

 

贴个代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

char map[2][11][11];
int vis[2][11][11];
int t,n,m;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node {
    int index;//层数
    int x,y;//坐标
    int time;
    friend bool operator <(const node &a,const node &b){
    //时间少的放在队列前面
        return a.time>b.time;
    }
};

int can_go(int index,int x,int y){
   if(x<0||x>=n||y<0||y>=m||map[index][x][y]==‘*‘){
    return 0;
   }
   return 1;
}

//bfs若time > T 则返回 -1
int bfs(int index,int x,int y){
    priority_queue<node>que;
    int i;
    node now,next;
    memset(vis,0,sizeof(vis));

    now.index=index;
    now.x=x;
    now.y=y;
    now.time=0;

    vis[index][x][y]=1;
    que.push(now);
    while(!que.empty()){
        now=que.top();
        que.pop();
        if(now.time>t){
            return -1;
        }
        if(map[now.index][now.x][now.y]==‘P‘){
            return 1;
        }
        for(i=0;i<4;i++){
            next.index=now.index;
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(!vis[next.index][next.x][next.y] && can_go(next.index,next.x,next.y)){
                vis[next.index][next.x][next.y]=1;
                if(map[next.index][next.x][next.y]==‘#‘&&!vis[!next.index][next.x][next.y]){


                    if(map[!next.index][next.x][next.y]==‘*‘||
                       map[!next.index][next.x][next.y]==‘#‘){
                        continue;
                    }
                    next.index=!next.index;
                    vis[next.index][next.x][next.y]=1;
                    next.time=now.time+1;
                    que.push(next);
                }
                else {
                    next.time=now.time+1;

                    que.push(next);
                }
            }
        }
    }
    return -1;
}

int main()
{
    int ans;
    int i;
    int c;
    scanf("%d",&c);
    while(c--){
        scanf("%d%d%d",&n,&m,&t);
        //printf("%d%d%d",n,m,t);
        for(i=0;i<n;i++){
            scanf("%s",map[0][i]);
        }
        for(i=0;i<n;i++){
            scanf("%s",map[1][i]);
        }

        ans=bfs(0,0,0);
        if(ans==-1){
            printf("NO\n");
        }
        else printf("YES\n");
    }
    return 0;
}




hdu 2102 A计划 具体题解 (BFS+优先队列)