攻击的最小数字所需 [英] Minimum numbers of attacks needed

问题描述

我们给出cells.Each细胞的2维栅格可以或可以不包含一个怪物

We are given 2 Dimensional grid of cells.Each cell may or may not contain a monster.

我们给出包含怪物小区列表

We are given a list of cells that contain monsters.

在一个单一的攻击，我们可以杀死所有的站在一排或一列中的怪物。我们 需要告诉攻击将需要消灭所有的怪物的最低数量。

In a single attack we can kill all the monsters standing in a row or in a column. We need to tell the minimum number of attacks that will be require to destroy all the monsters.

约束：

1 ≤ N ≤ 1000

1 ≤ X, Y ≤ 10^9

例如：

输入：

3

0 0

1 0

0 1

输出：

2

如何解决这个问题??

How to approach this problem..??

推荐答案

这可以看作是一个图的问题。

This can be modelled as a graph problem.

为每个行和列，其中有一个怪物的图的节点。 连接节点，如果一个怪物在该行和列。

Create a graph node for each row and column where there's a monster. Connect the nodes if a monster is on that row and that column.

这是一个二分图，你想要做的最小顶点覆盖。 柯尼希定理显示，对于二部图的问题是equivalnt具有最大匹配的问题，可以在polinomial时间来解决：

This is a bipartite graph, and you want to do minimum vertex cover. König's theorem shows that for bipartite graphs the problem is equivalnt with the maximum matching problem which can be solved in polinomial time:

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

这篇关于攻击的最小数字所需的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！