A计划 HDU - 2102

A计划  HDU - 2102

题目链接:https://vjudge.net/problem/HDU-2102

题目:

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在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

思路:bfs,三维坐标
//
// Created by hanyu on 2019/7/11.
//
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M,T;
struct node{
    int x,y,z;
    int dept;
};
int book[11][11][11];
int dic[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
char str[12][12][12];
bool bfs(int x,int y,int z)
{
    queue<node>qu;
    node now,next;
    now.x=x;
    now.y=y;
    now.z=z;
    now.dept=0;
    book[x][y][z]=1;
    qu.push(now);
    while(!qu.empty())
    {
        now=qu.front();
        qu.pop();
        if(str[now.x][now.y][now.z]==‘P‘)
            return true;
        if(now.dept>=T)
            return false;
        for(int i=0;i<4;i++)
        {
            int a=now.x;
            int b=now.y+dic[i][0];
            int c=now.z+dic[i][1];
            if(b<0||c<0||b>=N||c>=M||str[a][b][c]==‘*‘||book[a][b][c])
                continue;
            book[a][b][c]=1;
            if(str[a][b][c]==‘#‘)
            {
                a=!a;//传送到另一层
                if(str[a][b][c]==‘*‘||str[a][b][c]==‘#‘||book[a][b][c]==1)//遇到墙撞死,遇到#则无限循环
                    continue;
                book[a][b][c]=1;
            }
            next.x=a;
            next.y=b;
            next.z=c;
            next.dept=now.dept+1;
            qu.push(next);
        }

    }
    return false;
}
int main()
{
    int h;
    cin>>h;
    while(h--)
    {
        cin>>N>>M>>T;
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<N;j++)
            {
               scanf("%s",str[i][j]);
            }
        }
        memset(book,0,sizeof(book));
        if(bfs(0,0,0))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

    }
    return 0;
}

原文地址:https://www.cnblogs.com/Vampire6/p/11173365.html

时间: 07-11

A计划 HDU - 2102的相关文章

HDU 2102 A计划(BFS)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 题目大意:公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示.骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死.骑士们在一层中只能前后左右移动,每移动一格花1时刻.层间的移动只能通过时空传输机,且不需要任何时间.每个测试数据的前一行有三个整数N,M,T. N,M迷宫的大小N*

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;//层数

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;

HDU 2102 A计划 BFS

点击打开链接 A计划 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 10939    Accepted Submission(s): 2667 Problem Description 可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验.魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的

HDU 2102 A计划 (三维的迷宫BFS)

题目链接:pid=2102">传送门 题意: 三维的一个迷宫,起点在第一层的S(0,0,0)处,问是否能在规定的时间内走到第二层的P 处.'*'代表不能走,'.'代表能够走,'#'代表传送门,这里有一个trick,走到传送门的时 候必需要传送.之前没有注意到WA了非常多遍. 并且在初始的时候能够对地图进行一下处理,('*','#'),('#','*'),('#','#')这种肯定 是不能够走的,所以能够把他们都变成'*' 代码例如以下: #include <iostream>

HDU 2102 A计划 经典搜索

A计划 Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other) Total Submission(s) : 12   Accepted Submission(s) : 9 Font: Times New Roman | Verdana | Georgia Font Size: ← → Problem Description 可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她

HDU 2102 A计划 (BFS或DFS)

题意:中文题. 析:是一个简单的搜索,BFS 和 DFS都可行, 主要是这个题有一个坑点,那就是如果有一层是#,另一个层是#或者*,都是过不去的,就可以直接路过, 剩下的就是一个简单的搜索,只不过是两层而已,可能一个就是在#必须传送,这个题目已经说的很清楚了. 代码如下: BFS: #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string>

HDU 2102 A计划 _BFS

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #define CL(x,y) memset(x,y,sizeof(x)) 6 using namespace std; 7 struct node 8 { 9 int x; 10 int y; 11 int z; 12 int time; 13 }; 14 queue<node>

[hdu 2102]bfs+注意INF

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 感觉这个题非常水,结果一直WA,最后发现居然是0x3f3f3f3f不够大导致的--把INF改成INF+INF就过了. #include<bits/stdc++.h> using namespace std; bool vis[2][15][15]; char s[2][15][15]; const int INF=0x3f3f3f3f; const int fx[]={0,0,1,-1};

BFS专题

题目编号 OJ编号 题目名称 题解链接 Problem A HDU 1548 A strange lift http://www.cnblogs.com/ohyee/p/5389459.html Problem B HDU 1372 Knight Moves http://www.cnblogs.com/ohyee/p/5389471.html Problem C HDU 2717 Catch That Cow http://www.cnblogs.com/ohyee/p/5389479.htm