这是一个基于 Tetris 的谜题.在这个谜题中，我们给出了接下来 n 个将从顶部掉落的棋子的序列。我们的工作是在 GameOver 之前最大化分数。一般俄罗斯方 block 没有已知的多项式时间算法，但在这个谜题中只允许 I(直)tetrominoes。虽然不允许旋转它们。
所以这里是限制条件:
- 棋盘是一个宽 x 高的矩形
- 我们得到了下 n 个四联骨牌的序列
- 只允许 I 四联骨牌(水平或垂直)
- 不允许轮换
- 行被填满后被清除
- Board 最初是空的
- 每清除一行奖励 1 分。
- 当四联骨牌堆到比赛 field 的顶部时，游戏就结束了。
找出可以获得的最高分数。
例子:
8 x 6 板。接下来的 7 个四联骨牌是 [——,|,|,——,|,——,|] 其中 '——' 表示水平的 I 四联骨牌和 | 代表竖I四联。
在这种情况下，使用以下策略('.' 代表空棋盘，'#' 代表四联棋的一部分)的最大可能得分是 3。
Initially:
........
........
........
........
........
........
1st move:
........
........
........
........
........
####....
2nd Move:
........
........
.......#
.......#
.......#
####...#
3rd Move:
........
........
......##
......##
......##
####..##
4th Move:
........
........
......##
......##
####..##
####..##
5th Move:
........
........
.....###
.....###
####.###
####.###
6th Move:
........
........
.....###
####.###
####.###
####.###
7th Move:
........
........
....####
########
########
######## // bottom 3 rows are cleared so score is 3
final state:
........
........
........
........
........
....####
即使是我能想出的最好的算法也需要指数级的时间来保存当前板顶层的状态(即每列的高度)。因此，该算法将花费 O((H^W)*n) 时间，因为对于每一列，高度都有 H 种可能性。
可以使用动态规划或某些贪心算法在多项式时间内解决这个问题吗？
最佳答案
我来猜一猜:
棋盘是一个 W x H 二进制矩阵。
四联骨牌的序列是一个长度为n的二进制串s，1表示竖，0表示横。
让我们试试决策问题:给定任意棋盘和长度为 n 的任意序列 s 的四联骨牌，是否存在获胜序列？
在每一步你最多可以做 W 个选择:四联骨牌的位置。
要检查给定的棋盘和一系列四联骨牌是否存在移动的获胜序列，请使用以下算法检查 CanWin(B(n)):
CanWin(B(i)):
if Filled(B(i)) return false
if (i == n and not Filled(B(i))) return true
choose position in 0..W-1
B(i+1) = UpdateBoard(Bi, s(i+1), position)
return CanWin(B(i+1))
您可以通过检查顶行来检查板是否填充 O(W)。您可以通过检查 O(H) 中的碰撞来更新电路板。 [需要考虑行删除] 然后就可以在O(nW(H)^W)中判断是否有获胜序列。
如果您记得哪个猜测是父指针的最佳选择，那么您就有了一个成功的策略。
现在算法是指数的，但你可以 memoized数据集的递归，其大小最多为 2^(W x H + 1) x W。
从现在开始，我不知道如何计算内存电话的数量。
备注:
在此版本中，您无法在从顶部坠落的过程中引导四联骨牌。
由于行删除，递归中可能存在循环。你也许应该从你的问题中删除这条规则。
文章Tetris is Hard, Even to Approximate结论中的猜想，只有一个水平/垂直四联骨牌的俄罗斯方 block 是多项式时间。
关于algorithm - 俄罗斯方 block 拼图的多项式时间解决方案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31908143/