[Solved] Minimum numbers of attacks needed [closed]

Question

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.

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

Accepted Answer

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.

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