HDU_2102 A计划 【BFS】
2024-08-23 07:07:26
一、题目
二、题意分析
该题其实就是三位空间内的BFS,但比较简单的是,它设置了传送门,可以直接传送上去,需要注意的是
1.到了传送门的时候要重新考虑传送的点的三种情况。
(1)若又是传送门,这两个点都可以不再考虑了。
(2)若是墙,如题意,直接pass掉。
(3)若是P,找到了。
2.在T之前找到公主后也是可以的合理解释是不是骑士和公主可以在那里聊到T时刻?
三、AC代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <fstream>
#include <queue> using namespace std; int N, M, T;
const int dx[] = {, , , -};
const int dy[] = {, -, , };
char Map[][][];
bool visit[][][];
struct Node
{
int level, x, y;
}S, P;
// Node Q[1000000];
// int Rea, Cnt;
bool judge(Node t)
{
if(t.level < || t.level >= || t.x < || t.x >= N || t.y < || t.y >= M
|| Map[t.level][t.x][t.y] == '*' || visit[t.level][t.x][t.y] == )
return false;
return true;
} bool BFS()
{
memset(visit, , sizeof(visit));
queue<Node> Q;
Q.push(S); // Cnt = Rea = 0;
// Q[Cnt++] = S;
visit[S.level][S.x][S.y] = ; for(int t = ; t <= T; t++)
{
int size = (int)Q.size();
//int size = Cnt - Rea;
while(size--)
{
Node cur = Q.front();
Q.pop();
//Node cur = Q[Rea++]; for(int i = ; i < ; i++)
{
Node next = cur;
next.x += dx[i];
next.y += dy[i];
if(judge(next))
{
if(Map[next.level][next.x][next.y] == '#')
{
visit[next.level][next.x][next.y] = ;
next.level++;
next.level%=;
if(!judge(next))
continue;
}
if(Map[next.level][next.x][next.y] == '#')
{
visit[next.level][next.x][next.y] = ;
continue;
}
else if(Map[next.level][next.x][next.y] == 'P')
{
return true;
}
else
{
visit[next.level][next.x][next.y] = ;
Q.push(next);
}
//Q[Cnt++] = next;
}
}
}
}
return false; } int main()
{
//freopen("input.txt", "r", stdin);
int C;
scanf("%d", &C);
while(C--)
{
scanf("%d %d %d", &N, &M, &T);
for(int i = ; i < ; i++)
{
for(int j = ; j < N; j++)
{
scanf("%s", Map[i][j]);
for(int k = ; k < M; k++)
{
if(Map[i][j][k] == 'S')
{
S.level = i;
S.x = j;
S.y = k;
}
else if(Map[i][j][k] == 'P')
{
P.level = i;
P.x = j;
P.y = k;
}
}
}
getchar();
}
if(BFS())
printf("YES\n");
else
printf("NO\n");
}
return ;
}
最新文章
- Ubuntu 下安装QT
- Microsoft.CodeAnalysis 入门
- animate支持的css属性
- Raspberry pi之wifi设置-3
- mysql 存储过程 死循环,如何关闭
- .NET JSON对象序列化和反序列化
- 64位系统运行32位Oracle程序解决方案
- 在centos6.5中安装jdk
- SharePoint List 查看器
- ios系统 处理内存警告
- vs2010 mvc3创建的razor引擎模板页,子页面引用后出现当前上下文中不存在名称“ViewBag”
- 重操JS旧业第二弹:数据类型与类型转换
- Java学习8——类(对象)之间的关系
- web开发性能优化---分布式篇
- 基于python的接口自动化测试+ddt数据驱动
- 关于yaml语言
- Spark:大数据的电花火石!
- appium-基础搭建,适配,问题,优化,提速
- 2017.07.07【NOIP提高组】模拟赛B组
- [android] 手机卫士绑定sim卡