algorithm - 固定楼层算法

Question

好的，我有这个任务:约翰的浴室地板坏了。我们有这层楼的 map ，其中“.”是好盘，'+'是坏盘，例如:

.+++
.+.+

这里有 5 个损坏的盘子和 3 个完好的盘子。商店出售两种盘子:1x1 盘子和 2x1 盘子。 1x1 板材成本 A，2x1 板材成本 B。任务是:给定楼层 map ，计算地板固定的最低价格。

看上面的例子:我们可以放置 2 个 2x1 的盘子和 1 个 1x1 的盘子。所以价格将为 A+2*B。

我有一个想法:对每个断板计算连接断板的最大长度。那么价格是长度/2*B + 长度%2*A。

问题是，我真的不知道该怎么做。我有一些递归算法的想法，但是有这么多很多问题，比如圆圈:

+++
+.+
+++

所以我有两个问题:

1. 我的方向是否正确？
2. 你能给我一些关于实现这个算法的提示吗？

谢谢!

编辑

当 2*A < B 时存在平凡情况，但让我们谈谈非平凡 =)

/编辑

Answer 1

经典的平铺问题。这是一个加权精确覆盖，在非平凡的情况下(当使用两个 1x1 瓷砖比使用一个 1x2 瓷砖成本更高时)我会使用 ZDD 来解决它。找The Art of Computer Programming V4 1B举个例子(棋盘上的多米诺骨牌)。

有可用的库(例如 CUDD)，因此您不必从头开始实现 ZDD，尽管这也不是太难。

作为奖励，您还可以获得其他算法通常不提供的其他信息，例如无需全部枚举有效拼贴的数量。它还可以轻松推广到其他尺寸/形状的瓷砖(3x1、2x2、L 形等)。