【HDU - 2102】A计划（bfs）

时间：2023-03-09 23:45:57
【HDU - 2102】A计划（bfs）

-->A计划

Descriptions:

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。 
现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。


Input

输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。

Output

如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。

Sample Input

1

5 5 14

S*#*.

.#...

.....

****.

...#.

..*.P

#.*..

***..

...*.

*.#..

Sample Output

YES

题目链接：

https://vjudge.net/problem/HDU-2102

开个三维数组来存放地图，一样的bfs，只是在"#"的地方要换个位置，有个巧妙1的办法，比如说x表示底几层，那么x-1就可以表示在"#"的地方进行层次的切换

要注意从"#"跳转时，跳转的地方不能是"#"和"*"

具体操作看代码的注释

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

using namespace std;

int T,n,m,steps;

char mp[][][];//原始地图

int vis[][][];//记录人是否走过

int dt[][]= {{,},{-,},{,},{,-}};//四个方向

struct node

{

    int x,y,z;//坐标

    int step;//步数

};

node now,net;

void bfs()

{

    int f=;

    queue<node>q;

    MEM(vis,);//初始化

    now.x=,now.y=,now.z=,now.step=;

    q.push(now);

    vis[now.x][now.y][now.z]=;

    while(!q.empty())//开始老套路bfs

    {

        now=q.front();

        q.pop();

        if(mp[now.x][now.y][now.z]=='#')//特殊状态，传送门

        {

            now.x=-now.x;//0—>1 或者 1->0

            vis[now.x][now.y][now.z]=;//标记走过

            if(mp[now.x][now.y][now.z]=='*'||mp[now.x][now.y][now.z]=='#')//穿越过去是墙壁或者是传送门则不能走

                continue;

        }

        if(mp[now.x][now.y][now.z]=='P'&&now.step<=steps)//到达"P" 且步数不大于要求的步数即成功

        {

            f=;

            cout<<"YES"<<endl;

            break;

        }

        for(int i=; i<; i++)//四个方向，都老套路了

        {

            net.step=now.step+;//更新状态

            net.x=now.x;

            net.y=now.y+dt[i][];

            net.z=now.z+dt[i][];

            if(net.y>=&&net.y<n&&net.z>=&&net.z<m&&!vis[net.x][net.y][net.z]&&mp[net.x][net.y][net.z]!='*')//满足条件

            {

                q.push(net);

                vis[net.x][net.y][net.z]=;//标记走过

            }

        }

    }

    if(f==)

        cout<<"NO"<<endl;

}

int main()

{

    cin>>T;

    while(T--)

    {

        cin>>n>>m>>steps;//行 列 要求的步数

        for(int i=; i<; i++)//存地图吧

            for(int j=; j<n; j++)

                for(int k=; k<m; k++)

                    cin>>mp[i][j][k];

        bfs();

    }

}
相关文章