全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
如果没有楼梯,这个问题是一个经典的无权图的最短路问题。解法当然是宽搜。现在有了楼梯,普通的BFS不可行,需要改进。有两个改进方法,先看第一个。1.到达楼梯边缘P时,所经过的分钟数是奇数还是偶数会对是否上楼梯有所影响。我将达到P的最优解简称为最优解。那好,如果最优解时可过楼梯,那么从P达到楼梯的另一侧需要一分钟。如果不可过,那么需要等一分钟然后再用一分钟通过楼梯,这样P到达另一侧需要两分钟。此时, 已经将原问题转化成为带权图的最短路问题,Dij,SPFA,BF,任你选。复杂度:SPFA,O((MN)^2)2.重新表示状态,对于每个点,d[row][col][0]表示到达(row,col)点时的偶数最优解,
d[row][col][1]表示达到(row,col)点时的奇数最优解。这样,可以在d[row][col][0]和d[row][col][1]之间连一条权为1的边。在过楼梯时,如果奇数或者偶数解可过,则向楼梯的另一侧的奇数或者偶数点连一条权为1的边。这样,所有边的权都是1,仍然是无权图,还可以做宽搜
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 企业经营行业 财务基础入门作业指导书
- 企业员工绩效管理与激励作业指导书
- 商铺租赁合同
- 小学学业水平测试创意思维模拟试卷
- 部门体验工作心得体会(5篇)
- 小学冬令营测试试题
- 自由女神像的故事和象征意义
- 关于友谊的寓言故事
- 高中学习中的学业目标与实现途径
- 小学学业水平测试社科类模拟试卷
- 【医学课件】优生优育
- 花圃建设协议书范本
- 家长会课件:三年级家长会幻灯片
- 糖尿病的预防与治疗课件
- 关于申请清运垃圾车请示报告
- 粤港澳大湾区蓝皮书:粤港澳大湾区建设报告
- 建筑设计《中国古代建筑史》精美课件
- 2023-2024学年福建省厦门市海沧区重点学校九年级(上)第一次月考化学试卷(含解析)
- 提高电子体温单书写正确率
- 人教版七年级数学上册第一次月考测试卷(含答案)
- 社区戒毒(康复)人员档案
评论
0/150
提交评论