tło

Śluzowce są niesamowite. Jeśli umieścisz je na powierzchni ze źródłami żywności, rozłożą wąsy, aby znaleźć żywność, po czym utworzą sieć połączeń między źródłami. W tym wyzwaniu symulujesz śluzowatą pleśń szukającą pożywienia. Co więcej, ta konkretna pleśń zatrzyma się, gdy zostanie wystarczająco znaleziona.

Wejście

Twoje dane wejściowe powinny być listą Lwspółrzędnych całkowitych 2D w rodzimym formacie twojego języka i nieujemną liczbą całkowitą N. Lista Ljest na pewno wolna od duplikatów, ale nie można jej posortować. Wartość wejściowa Nwynosi od 0 do długości Lwłącznie.

Lista Lprzedstawia zestaw współrzędnych dla źródeł żywności. Na przykład lista

[(0,0),(2,-1),(3,1),(0,4),(5,5)]

może być interpretowane wizualnie jako

     o
o


   o
o
  o

Wynik

Twój wynik to kolejna pozbawiona duplikatów lista Kwspółrzędnych całkowitych 2D w tym samym formacie co dane wejściowe. Reprezentuje sieć utworzoną przez śluzowatą pleśń i musi spełniać następujące warunki:

• Przecięcie Li Kma dokładnie rozmiar N.
• Zestaw Kjest połączony jako podzbiór siatki liczb całkowitych (poprzez przylegania ortogonalne lub ukośne).
• Jeśli jakaś współrzędna z Kzostanie usunięta, nie spełnia już dwóch pierwszych warunków.

Zauważ, że jeśli N = 0, wyjście musi być pustą listą.

Przykładem akceptowalnego wyjścia dla powyższej listy Li N = 4byłoby

[(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)]

które mogą być wizualizowane jako

   xxO
Oxx
x  x
x  x
x  O
O
  o

gdzie każdy Oreprezentuje współrzędną zarówno Li K, a każdy xreprezentuje współrzędną w Kale nie L. Inne wyniki są również dopuszczalne, a „wąsy” nie muszą być możliwie najkrótsze. Na przykład jest to również akceptowalne rozwiązanie:

   xxOxx
Oxx     x
  x    x
 x    x
x  o x
O   x
  Ox 

Zasady

Zarówno dane wejściowe, jak i wyjściowe powinny być listami, a nie zestawami lub innymi typami danych. Współrzędne same mogą być listami lub krotkami. W razie potrzeby możesz zmienić kolejność dwóch wejść.

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

Twój program powinien działać na tych listach dla wszystkich odpowiednich wartości 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)]

Wizualizowane:

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

CJam, 77 95 bajtów

Myślę, że można to trochę pograć w golfa, ale oto:

q~$<_{{:X;]{[X\]z::-~mhW*}$~:Y{_)Y1{_@=X@=}:B~-g-{+__X=!\}:C~1B=!&}g{_(Y0B-g-\C0B=!&}g}*]_&}L?p

Wejście idzie jak N <Array of coordinate array>. Na przykład:

4 [[0 0] [1 5] [2 1] [0 3] [5 0] [5 5]]

Wynik:

[[0 5] [1 5] [0 4] [0 3] [0 0] [0 2] [0 1] [1 1] [2 1]]

Algorytm :

Algorytm jest dość prosty i wygląda następująco:

• Posortuj wejściową tablicę współrzędnych. To sprawia, że ​​współrzędne są sortowane najpierw według wiersza, a następnie według kolumny.
• Teraz wybieramy pierwsze Npunkty
• Teraz zmniejszamy te Npunkty. Miejsce docelowe jest ostatnim punktem, a źródłem jest punkt zamknięcia do tego ostatniego punktu.
• Następnie zaczynamy od lewego górnego punktu, idź w prawo (lub w lewo), aż znajdzie się na lub bezpośrednio nad następnym punktem.
• Następnie schodzimy do następnego punktu.
• Gwarantujemy, że do powyższego punktu w tym samym rzędzie nie pozostanie żaden odsłonięty punkt. Gwarantuje to, że nie dotykamy żadnego innego punktu niż wybrany N. Wybranie punktu zamknięcia zapewnia również, że druga reguła jest spełniona.

Wypróbuj online tutaj