Требуется минимальное количество атак

-5

Нам дана 2 размерная сетка ячеек. Каждая ячейка может содержать или не содержать монстра.Требуется минимальное количество атак

Нам дается список ячеек, содержащих монстров.

В одной атаке мы можем убить всех монстров, стоящих в строке или в столбце. Нам необходимо сообщить минимальное количество атак, которые потребуют уничтожить всех монстров.

Ограничения:

1 ≤ N ≤ 1000 

1 ≤ X, Y ≤ 10^9

Пример:

Вход:

Выход:

Как подойти к этой проблеме .. ??

источник

2013-10-04 user2826871

@Gray: он помечать его как алгоритм. «что ты пробовал?» вопрос по-прежнему актуальный, хотя –

- это сетка малонаселенная? В противном случае - длина самой короткой оси. – Jodrell

@ KarolyHorvath Я считал, что фактический язык может не иметь значения, но может быть полезно окончательно узнать, желателен он или нет. Не являются ли общие алгоритмы вне темы для SO? Не нужно ли быть «программным алгоритмом»? Я предполагал, что это различие означает, что для этого требуется какой-то код. – Gray

Это может быть смоделировано как проблема графа.

Создайте узел графа для каждой строки и столбца, где есть монстр. Подключите узлы, если монстр находится в этой строке и в этом столбце.

Это двудольный граф, и вы хотите сделать минимальное покрытие вершин. König's theorem показывает, что для двудольных графов проблема equivalnt с максимальными паросочетаниями, которая может быть решены в полиномиальное время:

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} }. Вы должны найти наименьший набор C в S, чей союз U.

источник

2013-10-04 13:58:38 ChronoTrigger

Этот ответ не показывает, что эта проблема эквивалентна задаче обложки. В этой задаче возможны не все множества S. Например, если * a * и * b *, но не * c * находятся в элементе из S, а * b * и * c *, но не * a * находятся в элементе из S, а * b * и * d * являются в элементе из S, то либо * d * находится в каждом элементе * a * и * b * в (одна и та же «строка» как * b * и * a *) или * d * находится в каждом элементе * b * и * c * находятся в (тот же «столбец», что и * b * и * c *). –

Я не хотел демонстрировать, что это была проблема с набором обложки, но она может быть смоделирована аналогичным образом.Есть подмножества, которые невозможны в S, но это не мешает вам писать S = {{a, b, d}, {b, c}} и решать SCP. – ChronoTrigger

Эта проблема не является NP-полной. –

Требуется минимальное количество атак

ответ

Смежные вопросы