Como amanhã é dia 4 de maio, aqui está uma pequena postagem com tema de Guerra nas Estrelas para prepará-lo mentalmente para todas as piadas ruins que virão amanhã.

BACKSTORY

Durante uma sessão do senado galáctico, todos os senadores estão sentados em uma n*ngrade. Um surto repentino de gripe JarJar (que dura para sempre e faz com que os infectados falem como JarJar Binks) faz com que alguns senadores sejam infectados.

Aqui está um exemplo com uma 6*6grade onde Xestão os senadores infectados, a lista correspondente é [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

Depois disso, a infecção começa a se espalhar passo a passo. Dois senadores são adjacentes se eles compartilham uma borda inteira na grade (ou seja, superior, inferior, direita, esquerda), o que significa que excluímos diagonais.

Podemos concluir que um senador pode estar adjacente a 2,3 ou 4 outros senadores e reivindicar as seguintes regras para a infecção:

• Um senador que foi infectado permanece infectado para sempre
• Um senador é infectado em uma etapa se estiver adjacente a 2 ou mais senadores infectados na etapa anterior

Aqui está um exemplo com a grade anterior, que mostra os 2 primeiros passos da infecção:

Após os próximos passos, todo o Senado será infectado

SUA TAREFA

Seu código não precisa manipular entradas inválidas, como uma lista maior n*nou coordenadas que não são distintas.

Seu código terá como entrada uma lista de pares de números inteiros (ou uma grade binária ou qualquer outro formato adequado ao seu idioma) e um número inteiro n(que pode ser desnecessário se você usar outro formato que não uma lista), por exemplo:

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

n sendo o lado da grade, o que significa que a grade será uma grade * n, e a lista de pares de números inteiros sendo as coordenadas das células dos senadores infectados inicialmente.

O canto inferior esquerdo da grade é [0,0] e o canto superior direito é [n-1, n-1]. O canto superior esquerdo é [0, n-1].

Seu código deve gerar um número inteiro:

-1 ou um valor falso ou um erro se a grade inteira nunca for totalmente infectada ou o número mínimo de etapas necessárias para infectar a grade inteira

Casos de teste

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

Lembre-se de que isso é código-golfe ; portanto, a resposta mais curta em bytes vence!

MATL, 29 28 bytes

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

A entrada está na forma de uma matriz 2D de 1 e 0

Experimente no MATL Online

Explicação

        % 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 caracteres ou 60 bytes

Pega a matriz fechada como argumento, retorna o número da etapa que completa a infecção, ou seja, 1 = já está totalmente infectado. 0 = não se espalha totalmente, que é apenas 1 + os números do OP.

54 caracteres (Unicode):

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

60 bytes (clássico):

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

⌺ é equivalente a ⎕U233A

Execução dos exemplos:

      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

Os passos são os seguintes:

┌─────────────┬──────────────────────────────────────────── ──────┬─────────────────────────────────┬──────────────── ────────────┐
│ 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 │
└───────────────────────────┴────────────────────────── ┴───────────────────────────┴────────────────────────── ┘

Pitão , 49 bytes

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

Conjunto de teste .

Usa indexação 1 para a saída.

Python, 231 bytes

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

Isso gera um erro se não for possível.

Experimente online!

JavaScript (ES6), 132 bytes

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

Onde \nrepresenta o caractere literal de nova linha. Toma de entrada como uma série de 0s e 1s em uma matriz delimitado por nova linha. Retorna NaNse a grade nunca será totalmente infectada.