思路:接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带你飞]专题二的更多相关文章
-
HDU - 3533 bfs [kuangbin带你飞]专题二
看了好久的样例才看懂. 题意:有一个人要从(0,0)走到(n,m),图中有k个碉堡,每个碉堡可以向某个固定的方向每隔t秒放一次炮,炮弹不能穿越另一个碉堡,会被阻挡.人在移动的过程中不会被炮弹打到,也就 ...
-
HDU - 1241 dfs or bfs [kuangbin带你飞]专题一
8个方向求联通块,经典问题. AC代码 #include<cstdio> #include<cstring> #include<algorithm> #includ ...
-
【算法系列学习三】[kuangbin带你飞]专题二 搜索进阶 之 A-Eight 反向bfs打表和康拓展开
[kuangbin带你飞]专题二 搜索进阶 之 A-Eight 这是一道经典的八数码问题.首先,简单介绍一下八数码问题: 八数码问题也称为九宫问题.在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的 ...
-
HDU - 3085 双向BFS + 技巧处理 [kuangbin带你飞]专题二
题意:有两只鬼,一个男孩女孩被困在迷宫中,男孩每秒可以走三步,女孩只能1步,鬼可以两步且可以通过墙.问男孩女孩是否可以在鬼抓住他们之前会合? 注意:每秒开始鬼先移动,然后两人开始移动. 思路:以男孩和 ...
-
HDU - 1067 Gap (bfs + hash) [kuangbin带你飞]专题二
题意: 起初定28张卡牌的排列,把其中11, 21, 31, 41移动到第一列,然后就出现四个空白,每个空白可以用它的前面一个数的下一个数填充,例如43后面的空格可以用44填充,但是47后面即 ...
-
HDU - 3567 Eight II (bfs预处理 + 康托) [kuangbin带你飞]专题二
类似HDU1430,不过本题需要枚举X的九个位置,分别保存状态,因为要保证最少步数.要保证字典序最小的话,在扩展节点时,方向顺序为:down, left, right, up. 我用c++提交1500 ...
-
HDU - 2612 bfs [kuangbin带你飞]专题一
分别以两个人的家作为起点,bfs求得到每个KFC最短距离.然后枚举每个KFC,求得时间之和的最小值即可. 此题不符合实际情况之处: 通过了一个KFC再去另一个KFC可以吗? 出题人都没好好想过吗? ...
-
HDU - 1495 bfs [kuangbin带你飞]专题一
模拟倒水的过程,每次可以把第i个杯子的水向第j个杯子里面倒,这可能出现新的状态,不停的更新状态,指导某两个杯子的水等于S/2说明找到答案,如果所有状态搜索完毕仍然不能均分,则退出. 注意:如果S是奇数 ...
-
【算法系列学习】[kuangbin带你飞]专题二 搜索进阶 D - Escape (BFS)
Escape 参考:http://blog.csdn.net/libin56842/article/details/41909459 [题意]: 一个人从(0,0)跑到(n,m),只有k点能量,一秒消 ...
随机推荐
-
在Ubuntu上为Android系统内置Java应用程序测试Application Frameworks层的硬件服务(老罗学习笔记6)
一:Eclipse下 1.创建工程: ---- 2.创建后目录 3.添加java函数 4.在src下创建package,在package下创建file 5.res---layout下创建xml文件,命 ...
-
BZOJ 2179FFT快速傅立叶
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2179 题目大意:给出两个n位10进制整数x和y,你需要计算x*y. 题解:FFT,不会的可以 ...
-
mac系统读写NTFS格式的移动硬盘
Mac OS X默认情况下,对于NTFS的移动硬盘只能读不能写,可通过将移动硬盘格式化为exFAT 或者安装NTFS相关的工具,达到可读写的目的,但对于系统的安全性方面,以上方式得不到保证:在Mac ...
-
关于Android路由的实现
先说一下背景,目前有需求从外部包括其他应用和WEB跳转到我们自己的APP,就这么个简单的需求-- 要实现这种外部跳转的功能,我们可以理解为打算跳转的一方有多少方式通知到APP进行相对的响应行为.所以, ...
-
ftk学习记(list篇)
[声明:版权全部,欢迎转载.请勿用于商业用途. 联系信箱:feixiaoxing @163.com] 在開始今天的list主题之前,先看一下icon的执行效果. 今天说的list事实上和这个icon几 ...
-
Intellij IDEA debug模式下项目启动慢/无法启动的事件解决过程记录
项目无法启动了 简单的介绍一下事件过程:周一的早上,收到前端同事抛过来的一个任务,说是一个接口无法正常返回数据,于是就让他把参数发过来,我想试着在本地重现一下并且将问题修复掉,这种情况肯定是要通过de ...
-
debian系linux墙内安装安全工具集
虽然有kali linux这样集合了很多安全工具的操作系统,但是kali的软件源相对老旧,没有ubuntu等主流debian系统丰富,kali默认使用su权限进入图形化界面也是违背linux权限机制的 ...
-
JavaScript Node节点笔记
1. 节点及其类型: 1). 元素节点 2). 属性节点: 元素的属性, 可以直接通过属性的方式来操作. 3). 文本节点: 是元素节点的子节点, 其内容为文本. 2. 在 html 文档的什么位置编 ...
-
支付宝支付Java代码
支付宝调用流程 开发前的准备工作 配置应用网关 应用网关里面填写的值就是商户后台的异步回调地址.也就是在支付宝付完款之后,由支付宝调用商户,便于商户验证订单各信息和更新订单状态 授权回调地址 授权回调 ...
-
bzoj3517 翻硬币
题意 有一个n行n列的棋盘,每个格子上都有一个硬币,且n为偶数.每个硬币要么是正面朝上,要么是反面朝上.每次操作你可以选定一个格子(x,y),然后将第x行和第y列的所有硬币都翻面.求将所有硬币都变成同 ...