请选择 进入手机版 | 继续访问电脑版

拯救公主 (Ver. I)

[复制链接]
盛夏丨光年丶 发表于 2021-1-2 19:47:51 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题解


  • 迷宫问题既可以用DFS也可以用BFS。DFS的优点在于方便得到起点到终点的准确路径,而BFS优点则是较为简单,且得到的路径长度是起点到终点的最短路径。
  1. ...xxxx.x.x....x.x.x..x...x..xxxxx........比如这个迷宫用DFS得到的就不是最短路径,而BFS在每增加一步时会包罗该步所有大概的通路,所以最先到终点的就一定最短路径。
复制代码
题目

[code]问题 E: 拯救公主 (Ver. I)时间限制: 1 Sec  内存限制: 128 MB提交: 112  办理: 30[提交][状态][讨论版]题目形貌公主被BEelzebub feng5166绑架,我们的英雄Ignatius必须拯救我们美丽的公主。现在他进入了feng5166的城堡。城堡是一个大型的迷宫。为了简单地办理这个问题,我们假设迷宫是一个N * M的二维数组,左上角是(0,0),右下角是(N-1,M-1)。Ignatius进入(0,0),feng5166房间的门是(N-1,M-1),这是我们的目的。这是一些规则:1.Ignatius只能向四个方向(上,下,左,右)移动,一步一秒。步调界说如下:如果当前位置为(x,y),则在步调之后,Ignatius只能站在(x-1,y),(x + 1,y),(x,y-1)或(X,Y + 1)。2.数组标有一些字符和数字,界说如下.:Ignatius可以走路的地方。X:这个地方是一个陷阱,Ignatius不能走在上面。你的任务是给出Ignatius到达目的位置所需的最小秒数。您可以假设起始位置和目的位置永远不会成为陷阱。输入测试数据有多组每个测试样例以包罗两个数字N和M(2
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )