当前位置:编程学习 > C/C++ >>

HDOJ 2102 A计划 (BFS)

这个题断断续续的做了好久,好无语……各种小细节的错,终于A掉了……
题意:从骑士从(0,0,0)点开始要在规定的T时间内到达P点(公主的位置)。每走一步要花一个单位的时间。‘.’是可走的路;‘*’是墙,不能走;‘#’是时空传输机,如果走上去就会被传送到另一层的相同位置(传送不耗费时间)。求其实能否在规定时间内救出公主。
思路:先将地图预处理,将不能走的点都标记成‘*’,然后BFS。
通过这道题让我认识到了两点:1、预处理有时候很重要,它可以减小之后的代码量,而且还不易使后面的代码因处理的情况太多而变得混乱;2、用队列(优先队列)处理多种情况时,务必记得要清空(如果内存够的话重开一个也可以)。
[cpp] 
#include<cstdio> 
#include<cstring> 
#include<queue> 
 
using namespace std; 
 
struct data 

    int floor,x,y,time; 
    friend bool operator < (data a,data b) 
    { 
        return a.time>b.time; //小的在前面 
    } 
}now,tmp; 
 
char maze[2][11][11]; 
bool vis[2][11][11]; 
 
int dx[]={0,1,0,-1}; 
int dy[]={1,0,-1,0}; 
 
int n,m,t; 
 
void remake() 

    for(int i=0;i<n;i++) 
    { 
        for(int j=0;j<m;j++) 
        { 
            if((maze[0][i][j]=='#'&&maze[1][i][j]=='#')||(maze[0][i][j]=='#'&&maze[1][i][j]=='*')||(maze[0][i][j]=='*'&&maze[1][i][j]=='#'))   
                maze[0][i][j]=maze[1][i][j]='*';   
        }   
    }   

 
int dfs() 

    priority_queue <struct data> q; 
    now.floor=now.x=now.y=now.time=0; 
    vis[0][0][0]=true; 
    q.push(now); 
    while(!q.empty()) 
    { 
        now=q.top(); 
        q.pop(); 
        if(now.time>t) 
            return -1; 
        if(maze[now.floor][now.x][now.y]=='#')//时空传输机 
        { 
            if(!vis[now.floor^1][now.x][now.y])//如果时空传输机到达的点没走过,则到达该点 
            { 
                now.floor^=1; 
                vis[now.floor][now.x][now.y]=true; 
            } 
            else 
                continue;//如果时空传输机到达的点已经走过,则不再往下运行 
        } 
        if(maze[now.floor][now.x][now.y]=='P') 
            return now.time; 
        for(int i=0;i<4;i++) 
        { 
            tmp.x=now.x+dx[i]; 
            tmp.y=now.y+dy[i]; 
            tmp.floor=now.floor; 
            tmp.time=now.time+1; 
            if(tmp.x>=0&&tmp.x<n&&tmp.y>=0&&tmp.y<m&&maze[tmp.floor][tmp.x][tmp.y]!='*'&&!vis[tmp.floor][tmp.x][tmp.y]) 
            { 
                vis[tmp.floor][tmp.x][tmp.y]=true; 
                q.push(tmp); 
            } 
        } 
    } 
    return -1; 

 
int main() 

    int c; 
    while(scanf("%d",&c)==1) 
    { 
        while(c--) 
        { 
            scanf("%d%d%d",&n,&m,&t); 
            memset(vis,false,sizeof(maze)); 
            for(int i=0;i<n;i++) 
            { 
                scanf("%s",maze[0][i]); 
            } 
            for(int i=0;i<n;i++) 
            { 
                scanf("%s",maze[1][i]); 
            } 
            remake();//预处理 
            int ret=dfs(); 
            if(ret!=-1) 
                printf("YES\n"); 
            else 
                printf("NO\n"); 
        } 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,