最强大脑第七季的一道题

小铃铛 · 发表于 2021-1-9 11:10:31

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

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

现要求你来精确导航，用最少的步数完成任务。

风云剑 · 发表于 2021-1-9 19:46:43

没啥思路，先尝试个完全搜索。还需要记录走过的位置，避免循环。好在看起来分支不算大，不知道全搜一遍靠不靠谱

aimisiyou · 发表于 2021-1-9 20:07:47

还没看懂游戏规则。

.·.·. · 发表于 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

向从简单的题着手，也许会简单一些：

小铃铛 · 发表于 2021-1-10 17:37:57

小铃铛发表于 2021-1-10 17:01
向从简单的题着手，也许会简单一些：

这道简单的题，最优解是40步：

账号		自动登录	找回密码
密码			欢迎注册

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

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

点评

点评