在此早期的问题中,OP询问了以下问题:
给定一个矩形网格,其中一些正方形是空的,有些正方形被填充,可以放入世界的最大数量的2x1多米诺骨牌是这样的,没有两个多米诺骨牌重叠,没有多米诺骨牌在填充的正方形上面？
(相当漂亮!)这个问题的答案认识到这相当于在特殊构造的图中找到最大的二分匹配.在此图中,每个空方块都有一个节点,该节点通过边链接到每个邻居.然后,每个多米诺骨牌对应于图中的边缘,使得其端点不被任何其他边缘覆盖.因此,不共享顶点(匹配)的任何边缘集合对应于多米诺骨牌的排列,反之亦然.
我的问题是对前一个问题的概括:
给定一个矩形网格,其中一些正方形是空的而一些是填充的,那么可以放入世界的M x N多米诺骨牌(对于给定的M和N)的最大数量是这样的,没有两个多米诺骨牌重叠并且没有多米诺骨牌在顶上一个满满的广场？
我无法看到如何将其转换为匹配问题,如前一种情况所做的那样.但是,我也没有看到为什么这个问题会立即成为NP难的特殊原因,因此可能存在一个多项式时间解决问题的方法.
有没有一种有效的算法来解决这个问题？或者是否有人有减少表明这个问题是NP难？
非常感谢!