博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 2102 A计划-bfs
阅读量:6274 次
发布时间:2019-06-22

本文共 3417 字,大约阅读时间需要 11 分钟。

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 11573    Accepted Submission(s): 2823

Problem Description
可 怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在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
 
#include 
#include
#include
#include
#include
using namespace std ;char mat1[12][12], mat2[12][12] ;//第一层和第二层int vis[12][12][2];//标记数组int dir[][2] = { {-1,0}, {
0,-1},{
1,0},{
0,1} } ;//方向int N, M, T ;struct node{ int x, y ; int f, st ;}sp, now, nex ;void _(){ scanf("%d%d%d",&N,&M,&T) ; for(int i = 0; i < N; ++i) scanf("%s",mat1[i]) ; for(int i = 0; i < N; ++i) scanf("%s",mat2[i]) ;}void bfs(){ queue
que ; vis[sp.x][sp.y][0] = 1 ;//根节点标记 que.push(sp) ; while(!que.empty()) { now = que.front() ; que.pop() ; if(now.f && mat2[now.x][now.y] == 'P') { if(now.st <= T) {printf("YES\n") ; return ;} else break ; } else if(!now.f && mat1[now.x][now.y] == 'P' ) { if(now.st <= T) {printf("YES\n") ; return ;} else break ; } for(int i = 0; i < 4; ++i) { nex.x = now.x + dir[i][0] ; nex.y = now.y + dir[i][1] ; nex.f = now.f ; nex.st = now.st + 1 ; if(nex.x < 0 || nex.x >= N || nex.y < 0 || nex.y >= M) continue ;//要先判断是否越界,再判断是否标记过 if(!nex.f && vis[nex.x][nex.y][0]) continue ;//标记过 else if(nex.f && vis[nex.x][nex.y][1]) continue ; if(nex.f && mat2[nex.x][nex.y] == '*') continue ;//是墙 else if(!nex.f && mat1[nex.x][nex.y] == '*') continue ; if(nex.f && mat2[nex.x][nex.y] == '.') { vis[nex.x][nex.y][1] = 1; que.push(nex) ; continue ;}//可以走 else if(!nex.f && mat1[nex.x][nex.y] == '.') { vis[nex.x][nex.y][0] = 1; que.push(nex) ; continue ;} //以下必不可少,在以前搜索迷宫的时候,我们是以 mat[i][j] != '*',来判断 (i,j)可以走,既若此时的节点为目标节点也同样入队 if(nex.f && mat2[nex.x][nex.y] == 'P') { //但在此处,我是分开判断,不加如下,目标节点反而会被舍弃 if(nex.st <= T) {printf("YES\n") ; return ;} else break ; } else if(!nex.f && mat1[nex.x][nex.y] == 'P') { if(nex.st <= T) {printf("YES\n") ; return ;} else break ; } if(nex.f && mat2[nex.x][nex.y] == '#'){ vis[nex.x][nex.y][1] = 1 ; if(mat1[nex.x][nex.y] == '*') continue ; if(mat1[nex.x][nex.y] == '#') continue ; if(mat1[nex.x][nex.y] == 'P') { //考虑传送之后直接到达目标节点的情况 if(nex.st <= T) {printf("YES\n") ; return ;} else break ; } nex.f = 0 ; que.push(nex) ; } if(!nex.f && mat1[nex.x][nex.y] == '#'){ vis[nex.x][nex.y][0] = 1 ; if(mat2[nex.x][nex.y] == '*') continue ; if(mat2[nex.x][nex.y] == '#') continue ; if(mat2[nex.x][nex.y] == 'P') { if(nex.st <= T) {printf("YES\n") ; return ;} else break ; } nex.f = 1 ; que.push(nex) ; } } } printf("NO\n") ;}void solve(){ _() ; sp.x = 0; sp.y = 0 ; sp.f = 0 ;sp.st = 0 ; memset(vis, 0 ,sizeof vis) ; bfs() ;}int main(){ // freopen("in.txt","r",stdin) ; int t ; scanf("%d",&t) ; while(t--) solve() ; return 0 ;}
View Code

 

Source
 

转载于:https://www.cnblogs.com/orchidzjl/p/4480368.html

你可能感兴趣的文章
JSON简介
查看>>
深圳安泰创新完成数千万新一轮融资,贝森资本领投
查看>>
当 Kubernetes 遇到阿里云
查看>>
MongoDB与Java 经典面试题、课程,好资源值得收藏
查看>>
标普全球获准进入中国市场,本土评级机构压力山大!
查看>>
阿里云基础产品技术月刊 2019年1月
查看>>
Go 语言的垃圾回收演化历程:垃圾回收和运行时问题
查看>>
苹果收购硅谷创业公司 Silk Labs,将继续布局 AI 和 IoT
查看>>
Idea开发Tomcat应用的热部署配置
查看>>
docker安装mysql
查看>>
GNOME 3.34 发布计划敲定,正式版将于9月11日推出
查看>>
使用Data Lake Analytics快速分析OSS上的日志文件
查看>>
《图解服务器端网络架构》笔记
查看>>
《叶问》第2期
查看>>
各业务Object概念(VO、 PO、DO、DTO、 BO、 QO、DAO、POJO)
查看>>
JavaScript对象继承方式
查看>>
Java 11中的新功能和API详解系列1
查看>>
网络编程懒人入门(九):通俗讲解,有了IP地址,为何还要用MAC地址?
查看>>
第三章 导数与微分
查看>>
WPF编游戏系列 之二 图标效果
查看>>