我们获得了二维网格单元,每个单元可能包含也可能不包含怪物。
我们将获得包含怪物的单元格列表。
在一次攻击中,我们可以杀死排成一列或一列的所有怪物。我们需要告诉消灭所有怪物所需的最小攻击次数。
限制条件:
1 ≤ N ≤ 1000 1 ≤ X, Y ≤ 10^9
例:
输入:
3 0 0 1 0 0 1
输出:
2
如何解决这个问题。
可以将其建模为图问题。
为每个有怪物的行和列创建一个图形节点。如果该行和该列上有怪物,则连接节点。
这是一个二部图,您想要做最小的顶点覆盖。柯尼希定理表明,对于二部图,该问题与最大匹配问题是等价的,可以在政治时间内解决该问题:
http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_graphs