HDU - 2102 A计划 (BFS) [kuangbin带你飞]专题二

时间:2021-12-30 22:55:20

思路:接BFS判断能否在限制时间内到达公主的位置,注意如果骑士进入传送机就会被立即传送到另一层,不会能再向四周移动了,例如第一层的位置(x, y, 1)是传送机,第二层(x, y, 2)也是传送机,这种情况骑士会一直被传上传下。

AC代码: 0ms

#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 15;
char G[2][maxn][maxn];
int d[2][maxn][maxn];
int n, m, Limit;

const int dx[] = {0,0,-1,1};
const int dy[] = {1,-1,0,0};
const int dz[] = {1,-1};

struct point{
	int x, y, z;
	point(){
	}
	point(int x, int y, int z):x(x), y(y), z(z){
	}
};

bool bfs() {
	memset(d, -1, sizeof(d));
	d[0][0][0] = 0;
	queue<point>q;
	q.push(point(0, 0, 0));
	while(!q.empty()) {
		point p = q.front();
		q.pop();
		int x = p.x, y = p.y, z = p.z;
		if(d[z][x][y] > Limit) return false;
		if(G[z][x][y] == 'P') return true;

		int flag = 0;
		if(G[z][x][y] == '#') { //传送机
			flag = 1;
			for(int i = 0; i < 2; ++i) {
				int pz = z + dz[i];
				if(pz < 0 || pz >= 2) continue;
				if(G[pz][x][y] == '*' || d[pz][x][y] != -1) continue;
				d[pz][x][y] = d[z][x][y];
				q.push(point(x, y, pz));
			}
		}
		if(flag) continue;

		for(int i = 0; i < 4; ++i) {
			int px = x + dx[i], py = y + dy[i];
			if(px < 0 || py < 0 || px >= n || py >= m) continue;
			if(d[z][px][py] != -1 || G[z][px][py] == '*') continue;
			d[z][px][py] = d[z][x][y] + 1;
			q.push(point(px, py, z));
		}
	}
	return false;
}
int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d%d", &n, &m, &Limit);
		for(int i = 0; i < 2; ++i) {
			for(int j = 0; j < n; ++j) scanf("%s", G[i][j]);
		}
		if(bfs()) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

如有不当之处欢迎指出!

HDU - 2102 A计划 (BFS) [kuangbin带你飞]专题二的更多相关文章

  1. HDU - 3533 bfs &lbrack;kuangbin带你飞&rsqb;专题二

    看了好久的样例才看懂. 题意:有一个人要从(0,0)走到(n,m),图中有k个碉堡,每个碉堡可以向某个固定的方向每隔t秒放一次炮,炮弹不能穿越另一个碉堡,会被阻挡.人在移动的过程中不会被炮弹打到,也就 ...

  2. HDU - 1241 dfs or bfs &lbrack;kuangbin带你飞&rsqb;专题一

    8个方向求联通块,经典问题. AC代码 #include<cstdio> #include<cstring> #include<algorithm> #includ ...

  3. 【算法系列学习三】&lbrack;kuangbin带你飞&rsqb;专题二 搜索进阶 之 A-Eight 反向bfs打表和康拓展开

    [kuangbin带你飞]专题二 搜索进阶 之 A-Eight 这是一道经典的八数码问题.首先,简单介绍一下八数码问题: 八数码问题也称为九宫问题.在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的 ...

  4. HDU - 3085 双向BFS &plus; 技巧处理 &lbrack;kuangbin带你飞&rsqb;专题二

    题意:有两只鬼,一个男孩女孩被困在迷宫中,男孩每秒可以走三步,女孩只能1步,鬼可以两步且可以通过墙.问男孩女孩是否可以在鬼抓住他们之前会合? 注意:每秒开始鬼先移动,然后两人开始移动. 思路:以男孩和 ...

  5. HDU - 1067 Gap &lpar;bfs &plus; hash&rpar; &lbrack;kuangbin带你飞&rsqb;专题二

    题意:    起初定28张卡牌的排列,把其中11,  21, 31, 41移动到第一列,然后就出现四个空白,每个空白可以用它的前面一个数的下一个数填充,例如43后面的空格可以用44填充,但是47后面即 ...

  6. HDU - 3567 Eight II &lpar;bfs预处理 &plus; 康托&rpar; &lbrack;kuangbin带你飞&rsqb;专题二

    类似HDU1430,不过本题需要枚举X的九个位置,分别保存状态,因为要保证最少步数.要保证字典序最小的话,在扩展节点时,方向顺序为:down, left, right, up. 我用c++提交1500 ...

  7. HDU - 2612 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    分别以两个人的家作为起点,bfs求得到每个KFC最短距离.然后枚举每个KFC,求得时间之和的最小值即可. 此题不符合实际情况之处:  通过了一个KFC再去另一个KFC可以吗? 出题人都没好好想过吗? ...

  8. HDU - 1495 bfs &lbrack;kuangbin带你飞&rsqb;专题一

    模拟倒水的过程,每次可以把第i个杯子的水向第j个杯子里面倒,这可能出现新的状态,不停的更新状态,指导某两个杯子的水等于S/2说明找到答案,如果所有状态搜索完毕仍然不能均分,则退出. 注意:如果S是奇数 ...

  9. 【算法系列学习】&lbrack;kuangbin带你飞&rsqb;专题二 搜索进阶 D - Escape &lpar;BFS&rpar;

    Escape 参考:http://blog.csdn.net/libin56842/article/details/41909459 [题意]: 一个人从(0,0)跑到(n,m),只有k点能量,一秒消 ...

随机推荐

  1. 在Ubuntu上为Android系统内置Java应用程序测试Application Frameworks层的硬件服务(老罗学习笔记6)

    一:Eclipse下 1.创建工程: ---- 2.创建后目录 3.添加java函数 4.在src下创建package,在package下创建file 5.res---layout下创建xml文件,命 ...

  2. BZOJ 2179FFT快速傅立叶

    传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2179 题目大意:给出两个n位10进制整数x和y,你需要计算x*y. 题解:FFT,不会的可以 ...

  3. mac系统读写NTFS格式的移动硬盘

    Mac OS X默认情况下,对于NTFS的移动硬盘只能读不能写,可通过将移动硬盘格式化为exFAT 或者安装NTFS相关的工具,达到可读写的目的,但对于系统的安全性方面,以上方式得不到保证:在Mac ...

  4. 关于Android路由的实现

    先说一下背景,目前有需求从外部包括其他应用和WEB跳转到我们自己的APP,就这么个简单的需求-- 要实现这种外部跳转的功能,我们可以理解为打算跳转的一方有多少方式通知到APP进行相对的响应行为.所以, ...

  5. ftk学习记(list篇)

    [声明:版权全部,欢迎转载.请勿用于商业用途. 联系信箱:feixiaoxing @163.com] 在開始今天的list主题之前,先看一下icon的执行效果. 今天说的list事实上和这个icon几 ...

  6. Intellij IDEA debug模式下项目启动慢&sol;无法启动的事件解决过程记录

    项目无法启动了 简单的介绍一下事件过程:周一的早上,收到前端同事抛过来的一个任务,说是一个接口无法正常返回数据,于是就让他把参数发过来,我想试着在本地重现一下并且将问题修复掉,这种情况肯定是要通过de ...

  7. debian系linux墙内安装安全工具集

    虽然有kali linux这样集合了很多安全工具的操作系统,但是kali的软件源相对老旧,没有ubuntu等主流debian系统丰富,kali默认使用su权限进入图形化界面也是违背linux权限机制的 ...

  8. JavaScript Node节点笔记

    1. 节点及其类型: 1). 元素节点 2). 属性节点: 元素的属性, 可以直接通过属性的方式来操作. 3). 文本节点: 是元素节点的子节点, 其内容为文本. 2. 在 html 文档的什么位置编 ...

  9. 支付宝支付Java代码

    支付宝调用流程 开发前的准备工作 配置应用网关 应用网关里面填写的值就是商户后台的异步回调地址.也就是在支付宝付完款之后,由支付宝调用商户,便于商户验证订单各信息和更新订单状态 授权回调地址 授权回调 ...

  10. bzoj3517 翻硬币

    题意 有一个n行n列的棋盘,每个格子上都有一个硬币,且n为偶数.每个硬币要么是正面朝上,要么是反面朝上.每次操作你可以选定一个格子(x,y),然后将第x行和第y列的所有硬币都翻面.求将所有硬币都变成同 ...