需要的最小攻击次数

-5

我们给出了2维网格的单元格。每个单元格可能包含或不包含怪物。需要的最小攻击次数

我们给出了一个包含怪物的单元格列表。

在单次攻击中，我们可以杀死连续或列中的所有怪物。我们需要告诉摧毁所有怪物将需要的最小攻击次数。

约束：

1 ≤ N ≤ 1000 

1 ≤ X, Y ≤ 10^9

例子：

输入：

输出：

如何处理这个问题..？

来源

2013-10-04 user2826871

@Gray：他标记它的算法。 “你有什么尝试？”问题仍然相关，虽然 –

是网格稀疏填充？否则，它是最短轴的长度。 – Jodrell

@KarolyHorvath我认为实际的语言可能并不重要，但它可以有助于明确地知道它是否合意。 SO不是一般的算法吗？它不需要成为“软件算法”吗？我认为这种区别意味着它需要一些代码。 – Gray

这可以建模为图形问题。

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

这是一个二部图，你想做最小顶点覆盖。 König's theorem表明，二部图的问题是equivalnt与可polinomial时间要解决的最大匹配的问题：

http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_graphs

来源

2013-10-04 14:09:21

这让我想起了Set Cover Problem：

您有一组U存储的N怪物：U = {1, 2, ..., N}，可能的攻击一套S。每次攻击都是攻击杀死怪物的一组索引。在你的例子中，S是S = { {1}, {2}, {}, {1}, {2} }。您必须在S中找到最小的集合C，其结合为U。

来源

2013-10-04 13:58:38 ChronoTrigger

这个答案没有证明这个问题相当于Set Cover Problem。在这个问题中，并不是所有的集合都是可能的。例如，如果* a *和* b *但不是* c *在S的元素中，并且* b *和* c *但不是* a *在S的元素中，并且* b *和* d *是在S的元素中，则* d *在每个元素* a *和* b *中（与* b *和* a *相同的“行”）或* d *在每个元素* b *中* c *在（与* b *和* c *相同的“列”中）。 –

我不想证明这是Set Cover Problem，但它可以用类似的方式建模。有些子集在S中是不可能的，但是这不会阻止你写S = {{a，b，d}，{b，c}}并解决SCP。 – ChronoTrigger

此问题不是NP完整的。 –

需要的最小攻击次数

回答

相关问题