数学研发论坛

 找回密码
 欢迎注册
查看: 195|回复: 7

[转载] 最强大脑第七季的一道题

[复制链接]
发表于 2021-1-9 11:10:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
智行营救
------------
一个不规则迷宫盘面内,每次按一下方向键(上下左右四个方向),红色色块就会沿指定方向的直线路径
行进至拐角,并将经过路径涂色。
选手需要在规定按键次数(以下称为步数)内将迷宫全部涂色。

现要求你来精确导航,用最少的步数完成任务。
109-00.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-9 19:46:43 | 显示全部楼层
没啥思路,先尝试个完全搜索。还需要记录走过的位置,避免循环。好在看起来分支不算大,不知道全搜一遍靠不靠谱

点评

这题的最优算法还是挺有意思的。当然,闲暇时间众人一起玩玩也很有意思。游戏界面简单,如果要最优化选择线路,会需要多些考虑了。  发表于 2021-1-9 22:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-9 20:07:47 | 显示全部楼层
还没看懂游戏规则。

点评

按方向键就累计一步,红色块就会沿着方向前进,直到这个方向上不能前进才停止下来。然后,你就需要选择一个方向再按方向键。红色块经过的路都会改变颜色。直到迷宫所有的路都改变了颜色,任务就算完成。  发表于 2021-1-9 21:55
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-1-10 05:30:47 | 显示全部楼层
风云剑 发表于 2021-1-9 19:46
没啥思路,先尝试个完全搜索。还需要记录走过的位置,避免循环。好在看起来分支不算大,不知道全搜一遍靠不 ...

我本来也想搜,但第一步就卡住了
我们并不能很方便地把问题化简成一个图,哪怕BFS找到所有可能停留的位置都不可行
(如果可行,这是一个有向图,A可以一步到达B未必代表B可以一步到达A)

考虑3x4的矩形,如果初始位置(2,2),第一步一定是到达(2,4)
但,有另一种方法遍历全部可能到达的8个位置:第一步到达(2,1),然后(1,1)(3,1)(3,4)(1,4)
此时(2,3)没有被染色

所以这个问题并没有那么容易搜
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-1-10 17:01:21 | 显示全部楼层
向从简单的题着手,也许会简单一些:
110-1.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-1-10 17:37:57 | 显示全部楼层
小铃铛 发表于 2021-1-10 17:01
向从简单的题着手,也许会简单一些:

这道简单的题,最优解是40步:
110-2.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-1-28 04:05 , Processed in 0.117486 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表