需要的最小攻擊次數

-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完整的。 –

需要的最小攻擊次數

回答

相關問題