Ponieważ jutro jest 4 maja, oto krótki post z motywem Gwiezdnych Wojen, aby przygotować się mentalnie na wszystkie złe żarty, które nadejdą jutro.

BACKSTORY

Podczas sesji galaktycznego senatu wszyscy senatorzy siedzą w n*nsiatce. Nagły wybuch grypy JarJar (trwający wiecznie i powodujący, że zarażeni mówią tak, jak JarJar Binks) powoduje zarażenie niektórych senatorów.

Oto przykład z 6*6siatką, w której Xsą zainfekowani senatorzy, odpowiednia lista to [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

Następnie infekcja zaczyna się rozprzestrzeniać krok po kroku. Dwóch senatorów sąsiaduje, jeśli dzielą całą krawędź siatki (tj. Góra, dół, prawo, lewa strona), co oznacza, że ​​wykluczamy przekątne.

Możemy stwierdzić, że senator może sąsiadować z 2,3 lub 4 innymi senatorami i zgłosić następujące zasady dotyczące infekcji:

• Zarażony senator pozostaje zarażony na zawsze
• Senator jest zarażany na jednym etapie, jeśli sąsiadował z 2 lub więcej zarażonymi senatorami na poprzednim etapie

Oto przykład z poprzednią siatką, która pokazuje 2 pierwsze kroki infekcji:

Po kolejnych krokach cały senat zostanie zainfekowany

TWOJE ZADANIE

Twój kod nie musi obsługiwać nieprawidłowych danych wejściowych, takich jak lista większa niż n*nlub współrzędne, które nie są różnicami.

Twój kod pobierze jako dane wejściowe listę par liczb całkowitych (lub siatkę binarną lub dowolny inny format, który pasuje do twojego języka) i liczbę całkowitą n(co może być niepotrzebne, jeśli używasz innego formatu niż lista), na przykład:

8 [[1,2],[1,1],[7,4],[2,7],[4,3]]

n jest stroną siatki, co oznacza, że ​​siatka będzie siatką * n, a lista par liczb całkowitych jest współrzędnymi komórek początkowo zainfekowanych senatorów.

Lewy dolny róg siatki to [0,0], a prawy górny - [n-1, n-1]. Lewy górny róg to [0, n-1].

Twój kod musi wypisywać liczbę całkowitą:

-1 lub wartość fałszowania lub błąd, jeśli cała sieć nigdy nie zostanie całkowicie zainfekowana lub minimalna liczba kroków wymaganych do zainfekowania całej sieci

Przypadki testowe

6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7

4 [[1,1][0,3][1,0][3,0][3,3]] => 9

Pamiętaj, że jest to golf golfowy , dlatego wygrywa najkrótsza odpowiedź w bajtach!

MATL, 29 28 bajtów

tn:"tlY6Z+1>Z|t?@.]]Nl=?l_]&

Dane wejściowe mają postać macierzy 2D z jedynkami i zerami

Wypróbuj w MATL Online

Wyjaśnienie

        % Implicitly grab user input as a 2D matrix
t       % Duplicate the inputs
n:      % Count the number of elements in the input (N) and create the array [1...N]
"       % Loop this many times (maximum number of steps we analyze)
  t     % Duplicate the top element
  lY6   % Push the 2D array => [0 1 0; 1 0 1; 0 1 0]
  Z+    % Perform 2D convolution (and maintain the size)
  l>    % Find all values that are >= 2
  Z|    % Perform an element-wise OR with the previous state
  t?    % If all elements are 1's
    @.  % Push the current index and break out of the loop
  ]     % End of if 
]       % End of for loop
Nl=?    % If there is only one element on the stack
  l_    % Push a negative one
]       % End of if statement
&       % Display the top stack element

APL (Dyalog 16.0), 54 znaki lub 60 bajtów

Jako argument przyjmuje zamkniętą macierz, zwraca numer kroku, który kończy infekcję, tzn. 1 = jest już w pełni zainfekowany. 0 = nie rozkłada się w pełni, co stanowi zaledwie 1 + numery PO.

54 znaki (Unicode):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

60 bajtów (Classic):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⎕U233A 3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

⌺ jest równa ⎕U233A

Przebieg przykładów:

      g←(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵ ⋄ (⊂f⊃⍵),⍵}⍣≡
      ⎕IO←0
      b←⊂⊖⍉~@(⎕JSON'[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]]')⊢0⍴⍨2⍴6
      g b
8
      b←⊂⊖⍉~@(⎕JSON'[[1,1],[0,3],[1,0],[3,0],[3,3]]')⊢0⍴⍨2⍴4
      g b
10

Kroki są następujące:

┌─────────────┬─────────────┬─────────────┬─────── ──────┬─────────────┬─────────────┬─────────────┬─ ────────────┐
│ XX │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │
│ X │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ │ X │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ X │ XX │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
└─────────────┴─────────────┴─────────────┴─────── ──────┴─────────────┴─────────────┴─────────────┴─ ────────────┘
┌─────────┬─────────┬─────────┬─────────┬───────── ┬─────────┬─────────┬─────────┬─────────┬───────── ┐
│ XX │ XX │ XX │ XX │ XX │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ │ │ │ │ X │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ X │ X │ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │ XXXX │
│ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │
└─────────┴─────────┴─────────┴─────────┴───────── ┴─────────┴─────────┴─────────┴─────────┴───────── ┘

Pyth , 49 bajtów

J^UE2*lK.uS{+NeMf>hT1r8S@Jsmm+VdkNs_MB_MBU2Q)qJeK

Zestaw testowy .

Używa 1-indeksowania dla danych wyjściowych.

Python, 231 bajtów

g=input()
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0
m=len(g);p=t=0;n=range(m)
while not all([r for k in g for r in k]):h=[[g[r][c]or sum([q(r+1,c),q(r-1,c),q(r,c+1),q(r,c-1)])>1 for c in n] for r in n];t+=1;0/(g!=h);g=h
print t

Zgłasza błąd, jeśli nie jest to możliwe.

Wypróbuj online!

JavaScript (ES6), 132 bajty

f=s=>(w=s.search`\n`,t=` `.repeat(w+1),t+=s+t,t=s.replace(/0/g,(_,i)=>1-t[i]-t[i+=w]-t[i+=2]-t[i+w]>>>31),t==s?0/!/0/.test(s):1+f(t))

Gdzie \nreprezentuje dosłowny znak nowej linii. Staje wejścia jako ciąg 0S i 1S w tablicy nowej linii rozdzielany. Zwraca, NaNjeśli siatka nigdy nie zostanie całkowicie zainfekowana.