hdoj1010 Tempter of the Bone(DFS迷宫)在规定时间内刚好到达

2023-10-09 11:48

本文主要是介绍hdoj1010 Tempter of the Bone(DFS迷宫)在规定时间内刚好到达,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:

hdoj1010

Problem Description

The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.

The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him.

Input

The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:

'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.

The input is terminated with three 0’s. This test case is not to be processed.

Output

For each test case, print in one line “YES” if the doggie can survive, or “NO” otherwise.

Sample Input

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0

Sample Output

NO
YES

题意:给出一个n*m的迷宫和时间t,图中X表示墙不能走过,S表示起点,D表示门,.表示可以走的路。每走一步需要1s,从S到D的时间不能大于t,也不能小于t,只能刚好等于t,不能回过头走重复的路,因为走完的路在1s之内就会塌陷,如果能够在规定时间刚好到达出口,则输出YES,否则就输出NO。
思路:先用字符二维数组a存迷宫,想好终止条件count > t和此时访问的刚好是D并且走过的时间刚好等于规定的时间,用一个success来标记有没有成功找到出口,如果在此时刚好访问到D并且走过的时间刚好等于规定的时间就标记success=true。在当前经历上为S或者.的时候,就将flag[sx][sy]标记为1,然后分别预测下一步是什么如果不超过数组范围并且没有访问过的话,就递归再深搜,这些条件写好后再回溯标记flag[sx][sy]为0,标记为未访问过,因为该点可以有多条路径经过,其实就是在枚举路径。

#include<iostream>
#include<cstdio>
#include<stack> 
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<map>using namespace std;char a[10][10];
int n,m,t;
int x,y;
int flag[10][10] = {0};
bool success;void dfs(int sx,int sy,int count) {if(count > t) {return;} else if(a[sx][sy] == 'D' && count == t) {success = true;return;} else if(a[sx][sy] == 'S' || a[sx][sy] == '.') {flag[sx][sy] = 1;
//		cout << sx << sy << endl; if(sy + 1 < m && flag[sx][sy + 1] == 0) dfs(sx,sy + 1,count + 1); //向右走一步 if(sy - 1 >= 0 && flag[sx][sy - 1] == 0) dfs(sx,sy - 1,count + 1); //向左走一步 if(sx + 1 < n && flag[sx + 1][sy] == 0) dfs(sx + 1,sy,count + 1); //向下走一步 if(sx - 1 >= 0 && flag[sx - 1][sy] == 0) dfs(sx - 1,sy,count + 1); //向上走一步 flag[sx][sy] = 0;}
}int main() {while(~scanf("%d%d%d",&n,&m,&t) && (m + n + t)) {for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {cin >> a[i][j];}}success = false;for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {flag[i][j] = 0;if(a[i][j] == 'S') {x = i;y = j;			}}}dfs(x,y,0);if(success) {printf("YES\n");} else {printf("NO\n");}}return 0;
}

这篇关于hdoj1010 Tempter of the Bone(DFS迷宫)在规定时间内刚好到达的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/172627

相关文章

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts?二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与

MyBatis Plus实现时间字段自动填充的完整方案

《MyBatisPlus实现时间字段自动填充的完整方案》在日常开发中,我们经常需要记录数据的创建时间和更新时间,传统的做法是在每次插入或更新操作时手动设置这些时间字段,这种方式不仅繁琐,还容易遗漏,... 目录前言解决目标技术栈实现步骤1. 实体类注解配置2. 创建元数据处理器3. 服务层代码优化填充机制详

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法

C# LiteDB处理时间序列数据的高性能解决方案

《C#LiteDB处理时间序列数据的高性能解决方案》LiteDB作为.NET生态下的轻量级嵌入式NoSQL数据库,一直是时间序列处理的优选方案,本文将为大家大家简单介绍一下LiteDB处理时间序列数... 目录为什么选择LiteDB处理时间序列数据第一章:LiteDB时间序列数据模型设计1.1 核心设计原则

MySQL按时间维度对亿级数据表进行平滑分表

《MySQL按时间维度对亿级数据表进行平滑分表》本文将以一个真实的4亿数据表分表案例为基础,详细介绍如何在不影响线上业务的情况下,完成按时间维度分表的完整过程,感兴趣的小伙伴可以了解一下... 目录引言一、为什么我们需要分表1.1 单表数据量过大的问题1.2 分表方案选型二、分表前的准备工作2.1 数据评估

MySQL中DATE_FORMAT时间函数的使用小结

《MySQL中DATE_FORMAT时间函数的使用小结》本文主要介绍了MySQL中DATE_FORMAT时间函数的使用小结,用于格式化日期/时间字段,可提取年月、统计月份数据、精确到天,对大家的学习或... 目录前言DATE_FORMAT时间函数总结前言mysql可以使用DATE_FORMAT获取日期字段

Python标准库datetime模块日期和时间数据类型解读

《Python标准库datetime模块日期和时间数据类型解读》文章介绍Python中datetime模块的date、time、datetime类,用于处理日期、时间及日期时间结合体,通过属性获取时间... 目录Datetime常用类日期date类型使用时间 time 类型使用日期和时间的结合体–日期时间(

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》:本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间