algorithm - NxN 二进制矩阵中有多少个 1x2 归零子矩阵？

Question

有多少（最多）1x2（或 2x1）归零子矩阵适合 NxN 二进制矩阵？

为了：

1 0 0
0 0 0
0 1 0

结果将是3。

为了：

0 0 1 0 0 1 0 0 0
0 1 0 1 0 1 0 1 1
1 0 0 1 0 1 1 0 1
0 1 1 0 1 0 1 0 0
0 0 0 0 1 0 1 1 0
1 1 1 1 0 0 1 0 0
1 0 0 1 1 1 1 1 1
0 0 1 1 0 0 0 0 0
1 0 0 1 0 0 1 1 0

结果将是21。

等等。

Answer 1

这可能不是最有效的方法，但解决此问题的一种简单方法是通过计算最大二分匹配，例如使用Hopfield-Karp 算法。

关键是将网格想象成一个棋盘，每个形状都会连接一个黑色方块和一个白色方块。

生成一个图，其中每个黑色方块有一个左节点，每个白色方块有一个右节点，以及从黑色方块节点到所有相邻白色方块节点的一条边。

此图中的最大匹配将是可以放置在网格中的非重叠多米诺骨牌的最大数量的答案。