假设方格纸上有一些数字。这个数字的两边直接在方格纸上。图可以具有任何（甚至不是凸起的）形状。如何找到可以放在该图中的最大多米诺骨牌（1x2矩形）。不允许将多米诺骨牌放在另一个上。当它的两侧正好落在方形纸的线条上时，允许以这种方式放置多米诺骨牌。
假设方格纸上有一些数字。这个数字的两边直接在方格纸上。图可以具有任何（甚至不是凸起的）形状。如何找到可以放在该图中的最大多米诺骨牌（1x2矩形）。不允许将多米诺骨牌放在另一个上。当它的两侧正好落在方形纸的线条上时，允许以这种方式放置多米诺骨牌。
看起来像 二分图中的最大基数匹配问题。正方形是顶点，多米诺骨牌是属于匹配的边。
要看到图表是二分图，想象正方形是棋盘画的。黑色只与白色相邻，反之亦然。
您可以使用邻居自由方格的数量将方块分类为类型0,1,2,3或4。
我认为应该有效：
找到一个1型方块，以唯一可能的方式放置多米诺骨牌并重复
另外，找到一个由两个连续的2型和3型正方形组成的自由角落，放置一个多米诺骨牌并转到1
否则，将多米诺骨牌放在任何类型2的方格中，然后转到1
你完成了