Saya penggemar berat game Creeper World, dan terutama sekuelnya. Anda tidak perlu tahu bagaimana game ini bekerja untuk menjawab pertanyaan, saya hanya ingin menyebutkan dari mana pertanyaan saya berasal.

Dalam gim, tujuan Anda adalah menghancurkan Emitter yang memunculkan Creeper, menggunakan senjata yang dikenal sebagai nullifier.

Nullifiers dapat menghancurkan emitor dalam radius ini:

 eee
eeeee
eenee
eeeee
 eee

Setiap nullifier BISA menargetkan beberapa Emitter.

Tujuan Anda

Diberikan array yang mensimulasikan peta 2D yang terdiri dari apa - apa dan penghasil emisi dengan karakter apa pun yang Anda suka, bisa berupa spasi dan e atau angka - pastikan saja mereka dapat dibedakan, output peta yang sama dengan jumlah optimal dari nullifiers n (atau apa yang Anda inginkan ) ditempatkan, sehingga emitor dihancurkan dengan jumlah paling sedikit dari nullifiers.

Jika ada beberapa cara optimal untuk melakukannya, hanya mengeluarkan satu akan baik-baik saja. Namun, jika tugas tersebut tidak dapat dipecahkan, katakanlah ada begitu banyak emitor yang tidak ada tata letak yang akan menghantam semuanya, Anda harus menampilkan sesuatu yang sangat berbeda, null akan mencukupi

Aturan Cepat:

• Input: array multidimensi
• Input akan berisi dua karakter, yang berarti apa - apa dan emitor , termasuk apa yang ada dalam jawaban Anda
• Output: array multidimensi
• Output akan berisi tiga karakter, yang berarti apa-apa , emitor dan nullifier ATAU output yang dapat dibedakan jika input tidak dapat dipecahkan
• Anda hanya dapat mengganti karakter kosong dengan nullifier
• Sebuah nullifier dapat mengenai banyak emitor, dan akan selalu mengenai semua yang ada dalam jangkauan
• Sebuah nullifier dapat mengenai area yang ditentukan di atas, dan akan selalu mengenai semua emitor yang dapat ditargetkan
• Jawaban terpendek dalam byte menang
• celah standar terlarang

Contohnya

Memasukkan:

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

Keluaran:

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

Memasukkan:

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

Keluaran:

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

Memasukkan:

[[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, ]]

Output (Output ini buatan tangan, dan mungkin bukan output yang optimal):

[[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, ]]

Memasukkan:

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

Keluaran:

null

Python 3 , 558 511 509 byte

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))

Cobalah online!

Ini sangat gila, tapi saya tidak cukup tahu tentang Python untuk mengoptimalkannya lebih lanjut. Saya memang belajar beberapa hal dari jawaban ovs, jadi itu menyenangkan.

Input (dimodifikasi untuk membuatnya lebih mudah untuk menulis kasus uji ) mengharapkan '' atau 'e', ​​sedangkan output menggunakan '', 'n' untuk nullifier, dan 'x' untuk emitor yang dibatalkan. Fungsi mengambil input yang diharapkan yang dijelaskan dalam pertanyaan.

Saya mengatur variabel e, w, n, dan d di luar karena mereka dapat dengan mudah diganti dengan angka dan, jika input dan output dimodifikasi untuk menggunakan angka juga, itu akan mencetak hal yang sama. Saya menggunakan huruf karena mereka membuatnya lebih mudah dibaca saat mengerjakannya.

Pertanyaan menyenangkan, OP! Creeper World hebat dan itu adalah inspirasi keren untuk pertanyaannya :)

Sunting: -47 bytes berkat Erik the Outgolfer

Python 2 , 267 263 byte

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)

Cobalah online!

0untuk emitor, 2untuk pembatal dan 1untuk ruang kosong.

Bahasa Wolfram (Mathematica) , 173 168 byte

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]]]

Cobalah online!

Memecahkan test case terbesar dalam 1 detik .

Program lengkap. Sebagai fungsi, ini lebih pendek, hanya 130 byte .

Gunakan 0untuk  , 1untuk ndan 2untuk e.

Program ini dapat digunakan untuk mengonversi dari format input dalam tantangan.

Jika tidak ada solusi, itu akan mencetak pesan kesalahan lpdimseperti ini , atau lpsnfseperti ini .

Versi yang menggunakan Outer(meskipun lebih mudah dibaca) adalah 2 byte lebih lama, meskipun nama pendeknya Outer: Coba online!

Penjelasan.

Perhatikan bahwa ini dapat dikurangi menjadi masalah pemrograman linear integer.

Setiap esel ditetapkan pada 2, setiap sel kosong adalah variabel integer, yang dapat berupa 0(kosong) atau 1(nullifier). Daftar koordinat variabel disimpan dalam variabel p. ( Positiondalam titu adalah 0)

Tujuannya adalah untuk meminimalkan jumlah nullifier yang digunakan, sehingga jumlah variabel integer tersebut harus diminimalkan. ( 1&/@p, vektor terdiri dari semua 1dan dengan panjang yang sama dengan ppanjangnya, menunjukkan fungsi objektif)

2q$\sqrt 6$

Ini dirumuskan dengan matriks m= (xBoole[Norm[x-#]^2<6]&/@p)/@q(untuk setiap elemen dalam q, buat baris dengan elemen menjadi 1jika jarak kuadrat ( Norm) ke koordinat yang sesuai di pkurang dari 6) dan vektor b= 1&/@q.

Setelah itu ReplacePartdan Thread"menerapkan" nilai variabel ke tdan mencetaknya.