首页 > 代码库 > hdu2102（bfs）

hdu2102（bfs）

2024-08-08 21:40:55   220人阅读

 

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

分析：bfs求最短时间到达‘P‘点，不过本题有好几个trick，我都踩到了，自己还是太嫩了。。。

        注意：可能两层同个位置都是‘#‘，还有经过‘#‘时只能被传送，不能经过它上下左右移动。。。

技术分享
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;int n,m,t;char s[2][15][15];struct node{    int x,y,z,step;    bool operator<(const node &a)const    {        return step>a.step;    }};int dx[]={1,-1,0,0,0,0};int dy[]={0,0,1,-1,0,0};int dz[]={0,0,0,0,1,-1};int vis[2][15][15],flag;node make_node(int a,int b,int c,int d){    node temp;    temp.x=a;temp.y=b;    temp.z=c;temp.step=d;    return temp;}int judge(int a,int b,int c){    return a>=0&&a<2&&b>=0&&b<n&&c>=0&&c<m&&!vis[a][b][c]&&s[a][b][c]!=‘*‘;}void bfs(int xx,int yy,int zz){    priority_queue<node>que;    while(!que.empty())que.pop();    memset(vis,0,sizeof(vis));    node cur,nxt;    vis[xx][yy][zz]=1;    que.push(make_node(xx,yy,zz,0));    while(!que.empty())    {        cur=que.top();que.pop();//进入队列的step不同步时，最好用优先队列保证最小步数出队        if(s[cur.x][cur.y][cur.z]==‘P‘)        {            if(cur.step<=t)flag=1;            return ;        }        for(int i=0;i<6;i++)        {            int x=cur.x+dx[i],y=cur.y+dy[i],z=cur.z+dz[i];            if(judge(x,y,z))            {                if(dx[i]&&s[cur.x][cur.y][cur.z]!=‘#‘)continue;//该位置可传送                if(dx[i]&&s[x][y][z]==‘#‘)continue;//两边都是传送机                if(s[cur.x][cur.y][cur.z]==‘#‘&&!dx[i])continue;//这里被坑了好久，不能左右上下移动了                vis[x][y][z]=1;                if(dx[i])                    que.push(make_node(x,y,z,cur.step));                else                    que.push(make_node(x,y,z,cur.step+1));            }        }    }}int main(){    int x,y,z,cas;    scanf("%d",&cas);    while(cas--)    {        scanf("%d%d%d",&n,&m,&t);        for(int i=0;i<=1;i++)        {            for(int j=0;j<n;j++)            {                scanf("%s",s[i][j]);            }        }        flag=0;        bfs(0,0,0);        if(flag)puts("YES");        else puts("NO");    }}
View Code

 

hdu2102（bfs）


联系
我们