热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

POJ3669题目解析:基于广度优先搜索的详细解答

POJ3669(http://poj.org/problem?id=3669)是一道典型的广度优先搜索(BFS)问题。由于陨石的降落具有时间属性,导致地图状态会随时间动态变化。因此,可以利用结构体来记录每个陨石的降落时间和位置,从而有效地进行状态更新和路径搜索。

POJ3669http://poj.org/problem?id=3669

很明显是一道bfs的题目

由于陨石的降临具有时刻性,所以地图是随时间变化的,

所以可以使用结构体来存储陨石下落的时刻以及位置以便更新地图然后预处理出安全位置(把会被轰炸的区域设置为2,把不会被轰炸的区域设置为1)

技术分享图片

由于陨石的轰炸不具有蔓延性(如果是火灾的蔓延则具有蔓延性),所以可以直接利用for循环更新地图,而人的移动具有蔓延性(即多方向延伸),所以需要用队列靠bfs更新)

接下来就是bfs操作

1、先把起点放进队列que,

技术分享图片

2、然后在bfs中用一个while(!que.empty)来维持搜索

技术分享图片

3、然后先通过时间判断是否开始轰炸更新地图(把轰炸区域设置为0),

技术分享图片

4、在引入时间轴之后,为了在时间更新之前,把每一步的操作全部遍历,引入que.size()

技术分享图片

5、再通过que.front();que.pop()读取并更新队列元素,并把合法的点(非“0”点)加入到队列,

技术分享图片

技术分享图片

6、此时别忘了把放入队列的点也设置为0,从而避免走回头路,

技术分享图片

7、最后更新时间

技术分享图片

技术分享图片

 


推荐阅读
  • 在 CentOS 6.5 系统上部署 VNC 服务器的详细步骤与配置指南
    在 CentOS 6.5 系统上部署 VNC 服务器时,首先需要确认 VNC 服务是否已安装。通常情况下,VNC 服务默认未安装。可以通过运行特定的查询命令来检查其安装状态。如果查询结果为空,则表明 VNC 服务尚未安装,需进行手动安装。此外,建议在安装前确保系统的软件包管理器已更新至最新版本,以避免兼容性问题。 ... [详细]
  • C# .NET 4.1 版本大型信息化系统集成平台中的主从表事务处理标准示例
    在C# .NET 4.1版本的大型信息化系统集成平台中,本文详细介绍了主从表事务处理的标准示例。通过确保所有操作要么全部成功,要么全部失败,实现主表和关联子表的同步插入。主表插入时会返回当前生成的主键,该主键随后用于子表插入时的关联。以下是一个示例代码片段,展示了如何在一个数据库事务中同时添加角色和相关用户。 ... [详细]
  • 并发编程入门:初探多任务处理技术
    并发编程入门:探索多任务处理技术并发编程是指在单个处理器上高效地管理多个任务的执行过程。其核心在于通过合理分配和协调任务,提高系统的整体性能。主要应用场景包括:1) 将复杂任务分解为多个子任务,并分配给不同的线程,实现并行处理;2) 通过同步机制确保线程间协调一致,避免资源竞争和数据不一致问题。此外,理解并发编程还涉及锁机制、线程池和异步编程等关键技术。 ... [详细]
  • Jeecg开源社区正式启动第12届架构技术培训班,现已开放报名。本次培训采用师徒制模式,深入探讨Java架构技术。类似于大学导师指导研究生的方式,特别适合在职人员。导师将为学员布置课题,提供丰富的视频资料,并进行一对一指导,帮助学员高效学习和完成任务。我们的教学方法注重实践与理论结合,旨在培养学员的综合技术能力。 ... [详细]
  • 在Ubuntu系统中配置Python环境变量是确保项目顺利运行的关键步骤。本文介绍了如何将Windows上的Django项目迁移到Ubuntu,并解决因虚拟环境导致的模块缺失问题。通过详细的操作指南,帮助读者正确配置虚拟环境,确保所有第三方库都能被正确识别和使用。此外,还提供了一些实用的技巧,如如何检查环境变量配置是否正确,以及如何在多个虚拟环境之间切换。 ... [详细]
  • 本文详细介绍了在 Vue.js 前端框架中集成 vue-i18n 插件以实现多语言支持的方法。通过具体的配置步骤和示例代码,帮助开发者快速掌握如何在项目中实现国际化功能,提升用户体验。同时,文章还探讨了常见的多语言切换问题及解决方案,为开发人员提供了实用的参考。 ... [详细]
  • 本文详细介绍了使用 Python 进行 MySQL 和 Redis 数据库操作的实战技巧。首先,针对 MySQL 数据库,通过 `pymysql` 模块展示了如何连接和操作数据库,包括建立连接、执行查询和更新等常见操作。接着,文章深入探讨了 Redis 的基本命令和高级功能,如键值存储、列表操作和事务处理。此外,还提供了多个实际案例,帮助读者更好地理解和应用这些技术。 ... [详细]
  • 如何高效利用Hackbar插件提升网页调试效率
    通过合理利用Hackbar插件,可以显著提升网页调试的效率。本文介绍了如何获取并使用未包含收费功能的2.1.3版本,以确保在不升级到最新2.2.2版本的情况下,依然能够高效进行网页调试。此外,文章还提供了详细的使用技巧和常见问题解决方案,帮助开发者更好地掌握这一工具。 ... [详细]
  • 开发了一款Windows API查看器,支持VBA语句导出,并提供超过两万个API的MSDN链接查询功能。
    开发了一款名为Windows API Viewer的工具,支持导出VBA语句,并集成了超过两万个API的MSDN链接查询功能,方便用户快速查找和使用相关API信息。 ... [详细]
  • 男性健康问题常常被忽视,许多人对疾病持轻视态度,即使出现症状也往往置之不理,认为会自行好转。然而,现代男性在健康管理方面应当重视医生的专业建议。以下是十个关键点,包括但不限于:胸口疼痛应及时就医、定期进行体检、保持合理饮食和适量运动等,以维护整体健康。 ... [详细]
  • 本指南旨在帮助Swoole初学者快速掌握异步并发编程的基本概念和实践方法。通过实例演示,我们将使用Swoole PHP扩展构建一个简单的客户端与服务器模型,并实现基本的通信功能。首先,我们将从客户端的实现入手(文件名为:client.php)。 ... [详细]
  • 在 Visual Studio 中,未选中文本时,使用 `Ctrl+X` 可以剪切并删除当前行,适用于快速删除整行代码;`Ctrl+C` 用于复制当前行的代码;`Ctrl+L` 则用于删除当前行。此外,通过组合键 `Ctrl+K, Ctrl+C` 可以注释选定的代码行,提升代码编辑效率。这些快捷键和技巧能够显著提高开发者的生产力,建议开发者熟练掌握并灵活运用。 ... [详细]
  • 在Android 4.4系统中,通过使用 `Intent` 对象并设置动作 `ACTION_GET_CONTENT` 或 `ACTION_OPEN_DOCUMENT`,可以从相册中选择图片并获取其路径。具体实现时,需要为 `Intent` 添加相应的类别,并处理返回的 Uri 以提取图片的文件路径。此方法适用于需要从用户相册中选择图片的应用场景,能够确保兼容性和用户体验。 ... [详细]
  • Docker入门指南:初探容器化技术
    Docker入门指南:初探容器化技术摘要:Docker 是一个使用 Go 语言开发的开源容器平台,旨在实现应用程序的构建、分发和运行的标准化。通过将应用及其依赖打包成轻量级的容器,Docker 能够确保应用在任何环境中都能一致地运行,从而提高开发和部署的效率。本文将详细介绍 Docker 的基本概念、核心功能以及如何快速上手使用这一强大的容器化工具。 ... [详细]
  • 使用for循环构建标准等腰三角形
    通过使用 `for` 循环,可以构建一个标准的等腰三角形。具体来说,每层的星号数量为 `2*i-1`,而空格的数量则为 `(n-i)*2`,其中 `n` 是总层数,`i` 是当前层的索引。通过合理地控制星号和空格的数量,可以确保生成的三角形在视觉上是标准且对称的。例如,对于一个 4 层的等腰三角形,第一层有 1 个星号和 6 个空格,第二层有 3 个星号和 4 个空格,依此类推。这种算法不仅简单高效,而且易于实现。 ... [详细]
author-avatar
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有