Jestem wielkim fanem gry Creeper World, a zwłaszcza kontynuacji. Nie musisz wiedzieć, jak działa ta gra, aby odpowiedzieć na pytanie, chciałem tylko wspomnieć, skąd pochodzi moje pytanie.

W grze Twoim celem jest zniszczenie Emiterów, które spawnują Creeper, przy użyciu broni znanej jako nullifier.

Nullifier może zniszczyć dowolny emiter w tym promieniu:

 eee
eeeee
eenee
eeeee
 eee

Każdy zerujący MOŻE celować w wiele Emiterów.

Twój cel

Biorąc pod uwagę tablicę symulującą mapę 2D składającą się z niczego i emiterów z dowolnymi znakami, które mogą ci się spodobać, mogą to być spacje i litery e lub liczby - po prostu upewnij się, że można je rozróżnić, wypisz tę samą mapę z optymalną ilością nullifierów n (lub tego, co chcesz ), tak aby emitery były niszczone przy użyciu najmniejszej liczby elementów unieważniających.

Jeśli istnieje wiele optymalnych sposobów na zrobienie tego, samo wyjście byłoby w porządku. Jeśli jednak zadania nie da się rozwiązać, powiedzmy, że jest tak wiele emiterów, że żaden układ nigdy nie trafi na wszystkie z nich, musisz wydać coś wyraźnie odróżniającego, wystarczy null

Szybkie zasady:

• Dane wejściowe: tablica wielowymiarowa
• Dane wejściowe będą zawierać dwa znaki, co oznacza, że nic, a emiter , uwzględni to, co znajduje się w odpowiedzi
• Dane wyjściowe: tablica wielowymiarowa
• Dane wyjściowe będą zawierać trzy znaki, co oznacza nic , emiter i nullifier LUB rozpoznawalne dane wyjściowe, jeśli danych wejściowych nie można rozwiązać
• Możesz zamienić znak „ nic” na nullifier
• Nullifier może trafić do wielu emiterów i zawsze trafi wszystkie znajdujące się w zasięgu
• Nullifier może trafić w wskazany powyżej obszar i zawsze trafi we wszystkie emitery, na które może celować
• Najkrótsze odpowiedzi w bajtach wygrywają
• standardowe luki zabronione

Przykłady

Wejście:

[[ , ,e, , ],
 [ , , , , ],
 [e, , , ,e],
 [ , , , , ],
 [ , ,e, , ]]

Wynik:

 [[ , ,e, , ],
  [ , , , , ],
  [e, ,n, ,e],
  [ , , , , ],
  [ , ,e, , ]]

Wejście:

[[e,e,e,e,e],
 [e, , , ,e],
 [e, , , ,e],
 [e, , , ,e],
 [e,e,e,e,e]]

Wynik:

[[e,e,e,e,e],
 [e, ,n, ,e],
 [e, , , ,e],
 [e, ,n, ,e],
 [e,e,e,e,e]]

Wejście:

[[e, , , , , , ,e, ,e, , , ,e, ,e, ,e, ,e],
 [ , ,e, , ,e, , , ,e,e, , , , ,e, , , , ],
 [ , ,e, , , ,e, ,e, ,e, ,e, ,e, ,e, , , ],
 [e, , , ,e, ,e, , , , , , , , , , , ,e, ],
 [e, , ,e, , , , , ,e, ,e, ,e, ,e, , , ,e],
 [ , , ,e, ,e, ,e, , , , , , , , , ,e, , ],
 [ ,e,e, ,e, , , ,e, ,e,e, ,e, ,e, ,e, , ],
 [ , ,e, , , ,e, , , , , , , , ,e,e, ,e, ],
 [ , , ,e, , , , ,e,e, , , , , , , , ,e, ],
 [e, , , , , , ,e, , , ,e,e, ,e, , , , , ],
 [ ,e,e, , ,e, , , , ,e, , , , , , ,e, , ],
 [ , , ,e,e, ,e, ,e, , , ,e,e, ,e, ,e, ,e],
 [e,e, , , , ,e, , , ,e, , , , , , , , , ],
 [ , , ,e, , , , , ,e, , ,e, ,e, ,e, ,e, ],
 [ , , , ,e, ,e, , , , , , , , , , , , , ],
 [e,e, , ,e,e, , ,e, , ,e, ,e, ,e, ,e, ,e],
 [e, ,e, ,e, , ,e,e,e, , ,e, , , ,e, , ,e],
 [ , , , ,e, , , , , ,e, , , ,e, , , , , ],
 [ , ,e, , , ,e, ,e, , , ,e, , , , ,e, , ],
 [ , , ,e, ,e, ,e, , ,e,e, , ,e,e, , ,e, ]]

Wyjście (To wyjście jest wykonane ręcznie i może nie być optymalnym wyjściem):

[[e, , , , , , ,e, ,e, , , ,e, ,e, ,e, ,e],
 [ , ,e, , ,e, , ,n,e,e, , , ,n,e, , , , ],
 [ ,n,e, , ,n,e, ,e, ,e, ,e, ,e, ,e, ,n, ],
 [e, , , ,e, ,e, , , , , , , , , , , ,e, ],
 [e, , ,e, , , , , ,e, ,e, ,e, ,e, , , ,e],
 [ , ,n,e, ,e, ,e, , , ,n, , , , , ,e, , ],
 [ ,e,e, ,e, ,n, ,e, ,e,e, ,e, ,e,n,e, , ],
 [ , ,e, , , ,e, , , , , , , , ,e,e, ,e, ],
 [ , , ,e, , , , ,e,e, , , , , , , , ,e, ],
 [e, ,n, , , , ,e, , , ,e,e, ,e, , , , , ],
 [ ,e,e, , ,e,n, , ,n,e, , , ,n, , ,e,e, ],
 [ , , ,e,e, ,e, ,e, , , ,e,e, ,e, ,e, ,e],
 [e,e, , , , ,e, , , ,e, , , , , , , , , ],
 [ , , ,e, ,n, , , ,e, , ,e, ,e, ,e, ,e, ],
 [ ,n, , ,e, ,e, , , , , , , ,n, , , ,n, ],
 [e,e, , ,e,e, , ,e,n, ,e, ,e, ,e, ,e, ,e],
 [e, ,e, ,e, , ,e,e,e, , ,e, , , ,e, , ,e],
 [ , , , ,e, , , , , ,e, ,n, ,e, , ,n, , ],
 [ , ,e, ,n, ,e, ,e, , , ,e, ,n, , ,e, , ],
 [ , , ,e, ,e, ,e, ,n,e,e, , ,e,e, , ,e, ]]

Wejście:

[[e,e],
 [e,e]]

Wynik:

null

Python 3 , 558 511 509 bajtów

from itertools import*
E=enumerate
L=len
def s(s):
 q=[(x,y)for y,r in E(s)for x,k in E(r)if k==w]
 for i in range(1,L(q)):
  for c in combinations(q,i):
   m=[l*1for l in s]
   for p in c:
    m[p[1]][p[0]]=n
    for y,r in E([list(r) for r in' xxx ,xxxxx,xxnxx,xxxxx, xxx '.split(',')]):
     for x,k in E(r):
      o=(p[0]-x+2,p[1]-y+2)
      if k==d and-1<o[0]<L(m[0])and-1<o[1]<L(m)and m[o[1]][o[0]]==e:
       m[p[1]-y+2][p[0]-x+2]=d
   if e not in ','.join([''.join(r)for r in m]):return(m)
print(s(m))

Wypróbuj online!

Jest bardzo zapętlony, ale nie wiem wystarczająco dużo o Pythonie, aby go dalej optymalizować. Nauczyłem się kilku rzeczy z odpowiedzi ovs, więc było fajnie.

Dane wejściowe (zmodyfikowane, aby ułatwić pisanie przypadków testowych ) oczekują „” lub „e”, podczas gdy dane wyjściowe używają „”, „n” dla nullifier i „x” dla nullified emiter. Funkcja przyjmuje oczekiwane dane wejściowe opisane w pytaniu.

Ustawiłem zmienne e, w, n i d na zewnątrz, ponieważ można je łatwo zastąpić liczbami, a jeśli dane wejściowe i wyjściowe zostałyby zmodyfikowane tak, aby używały również liczb, wydrukowałoby to samo. Użyłem liter, ponieważ dzięki temu były bardziej czytelne podczas pracy.

Zabawne pytanie, OP! Creeper World jest świetny i była fajną inspiracją do pytania :)

Edycja: -47 bajtów dzięki Erikowi Outgolfer

Python 2 , 267 263 bajtów

from itertools import*
m=input()
E=enumerate
e=[(x,y)for y,a in E(m)for x,e in E(a)if e]
for n in count():
 for p in combinations(e,n):
	k=[l*1for l in m]
	for x,y in p:k[y][x]=2
	all(e+any(8>(y-Y)**2+(x-X)**2for X,Y in p)for y,a in E(m)for x,e in E(a))>0>exit(k)

Wypróbuj online!

0dla emitera, 2zerowania i 1pustej przestrzeni.

Wolfram Language (Mathematica) , 173 168 bajtów

t=ToExpression@$ScriptInputString
P=Position
p=t~P~0
q=t~P~2
Print@ReplacePart[t,Thread[p->LinearProgramming[1&/@p,(xBoole[Norm[x-#]^2<6]&/@p)/@q,1&/@q,0,Integers]]]

Wypróbuj online!

Rozwiązuje największy przypadek testowy w ciągu 1 sekundy .

Pełny program Jako funkcja jest krótsza, ma tylko 130 bajtów .

Użyj 0dla  , 1dla ni 2dla e.

Tego programu można użyć do konwersji z formatu wejściowego w wyzwaniu.

Jeśli istnieją żadne rozwiązanie nie będzie drukować komunikat o błędzie lpdimjak to , czy lpsnfjak ten .

Wersja używająca Outer(choć bardziej czytelna) jest o 2 bajty dłuższa, pomimo krótkiej nazwy Outer: Wypróbuj online!

Wyjaśnienie.

Zauważ, że można to sprowadzić do problemu programowania liniowego na liczbach całkowitych.

Każda ekomórka jest ustalona na 2, każda pusta komórka jest zmienną całkowitą, która może być 0(pusta) lub 1(nullifier). Lista współrzędnych zmiennych jest przechowywana w zmiennej p. ( Positionw ttym jest 0)

Celem jest zminimalizowanie liczby użytych zerowania, więc suma tych zmiennych całkowitych musi zostać zminimalizowana. ( 1&/@pwektor składa się ze wszystkich 1i ma długość równą pdługości, wskazuje funkcję celu)

2q$\sqrt 6$

Jest to sformułowane z macierzą m= (xBoole[Norm[x-#]^2<6]&/@p)/@q(dla każdego elementu w q, utwórz wiersz z elementami, 1jeśli kwadratowa odległość ( Norm) do odpowiedniej współrzędnej pjest mniejsza niż 6), a wektor b= 1&/@q.

Po tym ReplaceParti Thread„Dotyczy” wartości zmiennej, ta następnie je wydrukować.