algorithm - 所需的最少攻击次数

Question

我们得到了二维网格单元格。每个单元格可能包含也可能不包含怪物。

我们得到一个包含怪物的单元格列表。

在一次攻击中，我们可以杀死所有排成一排或一列的怪物。我们需要知道摧毁所有怪物所需的最少攻击次数。

约束：

1 ≤ N ≤ 1000

1 ≤ X, Y ≤ 10^9

例子：

输入：

输出：

如何解决这个问题..？

score 3 · Accepted Answer

这可以建模为图问题。

为存在怪物的每一行和每一列创建一个图形节点。如果怪物在该行和该列上，则连接节点。

这是一个二分图，你想做最小的顶点覆盖。König 定理表明，对于二部图，该问题等价于可以在多项式时间内解决的最大匹配问题：

score 0 · Accepted Answer

这让我想起了Set Cover 问题：

你有一个U存储N怪物的集合：U = {1, 2, ..., N}，一组S可能的攻击。每次攻击也是该攻击杀死的怪物的一组指标。在您的示例中，S是S = { {1}, {2}, {}, {1}, {2} }. 您必须找到其并集为C的最小集合。SU

2 回答 2