Latar Belakang
Cetakan lendir mengagumkan. Jika Anda meletakkannya di permukaan dengan sumber makanan, mereka akan menyebarkan sulurnya untuk menemukan makanan, setelah itu mereka membentuk jaringan koneksi antar sumber. Dalam tantangan ini, Anda harus mensimulasikan cetakan lendir mencari makanan. Selain itu, cetakan khusus ini akan berhenti setelah cukup ditemukan.
Memasukkan
Input Anda harus berupa daftar Lkoordinat bilangan bulat 2D dalam format asli bahasa Anda, dan bilangan bulat tidak negatif N. Daftar Lini dijamin bebas duplikat, tetapi mungkin tidak disortir. Inputnya Nantara 0 dan panjang L, inklusif.
Daftar ini Lmewakili seperangkat koordinat untuk sumber makanan. Misalnya, daftarnya
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
dapat diartikan secara visual sebagai
o
o
o
o
o
Keluaran
Output Anda adalah daftar bebas-duplikat lain Kdari koordinat integer 2D pada format yang sama dengan input. Ini mewakili jaringan yang dibentuk oleh cetakan lendir, dan harus memenuhi kondisi berikut:
- Persimpangan
LdanKmemiliki ukuran persisN. - Set
Kterhubung sebagai subset dari grid integer (melalui adjacency ortogonal atau diagonal). - Jika ada koordinat
Kyang dihapus, maka tidak lagi memenuhi dua kondisi pertama.
Perhatikan bahwa jika N = 0, output harus berupa daftar kosong.
Contoh output yang dapat diterima untuk daftar di atas Ldan N = 4akan menjadi
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,4),(2,4),(3,3),(3,2),(3,1),(3,5),(4,5),(5,5)]
yang dapat divisualisasikan sebagai
xxO
Oxx
x x
x x
x O
O
o
di mana masing-masing Omewakili koordinat di keduanya Ldan K, dan masing-masing xmewakili koordinat di Ktetapi tidak di L. Keluaran lain juga dapat diterima, dan "sulur" tidak harus sesingkat mungkin. Misalnya, ini juga merupakan solusi yang dapat diterima:
xxOxx
Oxx x
x x
x x
x o x
O x
Ox
Aturan
Baik input dan output harus berupa daftar, bukan set atau tipe data lainnya. Koordinat itu sendiri dapat berupa daftar atau tupel. Anda dapat mengubah urutan kedua input jika perlu.
Anda dapat menulis program lengkap atau fungsi. Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Uji Kasus
Program Anda harus mengerjakan daftar ini untuk semua nilai yang berlaku dari N.
[]
[(2,3)]
[(0,0),(1,0),(0,1),(1,1)]
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3),(0,1),(0,2),(3,1),(3,2),(8,1),(8,2),(-5,1),(-5,2)]
[(0,0),(20,0),(15,15),(-10,4),(-10,3),(0,-5),(7,6),(7,7),(8,8),(9,8),(10,-2),(-1,12),(-3,10)]
[(0,0),(1,0),(2,0),(3,0),(5,0),(6,0),(7,0),(0,9),(1,9),(2,9),(3,8),(4,9),(5,10),(6,10),(7,9),(3,3),(4,4),(5,5)]
Divisualisasikan:
===
o
===
oo
oo
===
o
o
o
o
o
===
oooo
oooo
===
oooo
o o o o
o o o o
oooo
===
o
o
o
oo
o
o
o
o
o o
o
o
===
oo
ooo o o
o
o
o
o
oooo ooo
sumber