Como mañana es el 4 de mayo, aquí hay una pequeña publicación temática de Star Wars para prepararte mentalmente para todos los chistes malos que vendrán mañana.

TRASFONDO

Durante una sesión del senado galáctico, todos los senadores están sentados en una n*ncuadrícula. Un brote repentino de gripe JarJar (que dura para siempre y hace que los infectados hablen como JarJar Binks) hace que algunos de los senadores se infecten.

Aquí hay un ejemplo con una 6*6cuadrícula donde Xestán los senadores infectados, la lista correspondiente es [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

Después de eso, la infección comienza a extenderse paso a paso. Dos senadores son adyacentes si comparten un borde completo en la cuadrícula (es decir, arriba, abajo, derecha, izquierda), lo que significa que excluimos las diagonales.

Podemos concluir que un senador puede ser adyacente a 2,3 o 4 otros senadores y reclamar las siguientes reglas para la infección:

• Un senador que ha sido infectado permanece infectado para siempre.
• Un senador se infecta en un paso si estaba adyacente a 2 o más senadores infectados en el paso anterior

Aquí hay un ejemplo con la cuadrícula anterior que muestra los 2 primeros pasos de la infección:

Después de los siguientes pasos, todo el Senado se infectará.

TU TAREA

Su código no necesita manejar entradas inválidas como una lista mayor n*no coordenadas que no son distintivas.

Su código tomará como entrada una lista de pares de enteros (o una cuadrícula binaria o cualquier otro formato que se adapte a su idioma) y un entero n(que puede ser innecesario si usa otro formato que no sea una lista), por ejemplo:

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

n es el lado de la cuadrícula, lo que significa que la cuadrícula será una * n cuadrícula, y la lista de pares de enteros son las coordenadas de las celdas de los senadores infectados inicialmente.

La parte inferior izquierda de la cuadrícula es [0,0] y la parte superior derecha es [n-1, n-1]. La esquina superior izquierda es [0, n-1].

Su código debe generar un número entero:

-1 o un valor falso o un error si la cuadrícula completa nunca se infectará totalmente o el número mínimo de pasos necesarios para infectar toda la cuadrícula

Casos de prueba

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

Recuerde que esto es código golf , por lo tanto, ¡la respuesta más corta en bytes gana!

MATL, 29 28 bytes

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

La entrada tiene la forma de una matriz 2D de 1 y 0

Pruébalo en MATL Online

Explicación

        % 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 o 60 bytes

Toma la matriz adjunta como argumento, devuelve el número de paso que completa la infección, es decir, 1 = ya está completamente infectado. 0 = no se extiende completamente, que es solo 1 + los números del OP.

54 caracteres (Unicode):

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

60 bytes (clásico):

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

⌺ es equivalente a ⎕U233A

Ejecución de ejemplos:

      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

Los pasos son los siguientes:

┌─────────────┬─────────────┬─────────────┬─────── ──────┬─────────────┬─────────────┬─────────────┬─ ────────────┐
│ 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 bytes

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

Banco de pruebas .

Utiliza 1 indexación para la salida.

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

Provoca un error si no es posible.

Pruébalo en línea!

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

Donde \nrepresenta el carácter de nueva línea literal. Toma de entrada como una cadena de 0s y 1s en una matriz de nueva línea delimitado. Devuelve NaNsi la cuadrícula nunca se infectará por completo.