Supongamos que tenemos una matriz como esta:

11111
12221
12321
12221
11111

Esta matriz representa un terreno, y cada celda representa una parte del terreno. El número en cada celda representa el tiempo que la porción de terreno necesita quemarse por completo (en minutos, si se necesita una unidad de medida), de acuerdo con su combustibilidad . Si un incendio comienza en cualquier posición (celda), esa celda debe quemarse por completo antes de que el fuego se propague a las celdas adyacentes (solo horizontal y vertical, no diagonal). Entonces, si se inicia un incendio en la posición central, el incendio necesita:

11111        11111        11111        11011        10001        00000
12221  3 m.  12221  2 m.  12021  1 m.  11011  1 m.  00000  1 m.  00000
12321 -----> 12021 -----> 10001 -----> 00000 -----> 00000 -----> 00000
12221        12221        12021        11011        00000        00000
11111        11111        11111        11011        10001        00000

Explicación:

• El fuego comienza en [2,2] (basado en 0), que tiene un tiempo de combustión de 3.
• Después de 3 minutos, [1,2], [2,1], [2,3], [3,2] comienzan a arder.
• Después de 2 minutos, esas celdas terminan quemándose y el fuego se propaga a todas las celdas adyacentes, pero [0,2], [2,0], [2,4], [0,4] necesitan solo 1 minuto más para quemar, así que
• Después de 1 minuto, esas células se queman y la célula se propaga a sus células adyacentes.
• Después de 1 minuto más, el resto de las celdas del paso 3 terminan quemándose y el fuego se propaga a sus celdas adyacentes (que ya están quemadas, por lo que no sucede nada).
• Después de 1 último minuto, el fuego termina quemando todo el terreno.

Entonces la solución a ese caso es de 8 minutos. Si el fuego comienza en la celda superior izquierda [0,0]:

11111     01111     00111     00011     00001     00000
12221  1  12221  1  02221  1  01221  1  00121  1  00011   1
12321 --> 12321 --> 12321 --> 02321 --> 01321 --> 00321  -->
12221     12221     12221     12221     02221     01221
11111     11111     11111     11111     11111     01111

00000     00000     00000     00000     00000
00000  1  00000  1  00000  1  00000  1  00000
00221 --> 00110 --> 00000 --> 00000 --> 00000
00221     00121     00020     00010     00000
00111     00011     00001     00000     00000

Entonces ahora el tiempo total es de 10 minutos.

El reto

Dada una matriz NxM (N> 0, M> 0) de valores enteros que representan el tiempo que cada celda necesita ser completamente consumida, escriba el programa / función más corto que tome esa matriz y un par de enteros con la posición en la que comienza el fuego , y devuelve / imprime el tiempo necesario para que el fuego consuma por completo todo el terreno.

• Cada celda tendrá un tiempo de grabación positivo (no cero). No puede asumir un valor máximo para las celdas.
• La matriz no necesita ser cuadrada ni simétrica.
• La matriz puede ser indexada 0 o indexada 1, como desee.
• La posición se puede dar como un parámetro único con una tupla de enteros, dos parámetros separados de cualquier otro formato razonable.
• Las dimensiones de la matriz no se pueden especificar como parámetros de entrada.
• No necesita generar cada paso intermedio, solo la cantidad de tiempo solicitada. Pero no me quejaré si los pasos se visualizan de alguna manera.

Otro ejemplo:

Fire starts at [1,1] (a '>' represents a minute):

4253   4253   4253   4153   4043   3033   2023    0001   0000
2213 > 2113 > 2013 > 1003 > 0002 > 0001 > 0000 >> 0000 > 0000 
1211   1211   1211   1111   1001   0000   0000    0000   0000

Output: 9

Este es el código de golf , por lo que puede ganar el programa más corto para cada idioma

Matlab, 235 257 190 182 178 bytes

Entrada: matriz A, vector 1x2 que pcontiene las coordenadas iniciales.

function t=F(A,p)
[n,m]=size(A);x=2:n*m;x(mod(x,n)==1)=0;B=diag(x,1)+diag(n+1:n*m,n);k=sub2ind([n m],p(1),p(2));t=max(distances(digraph(bsxfun(@times,((B+B')~=0),A(:))'),k))+A(k)

Explicación:

En lugar de simular la propagación del fuego, también podemos entender esto como un problema de "encontrar el camino más largo más corto". La matriz se convierte en un gráfico dirigido ponderado. Los pesos de las rutas a un solo nodo corresponden al tiempo para quemar dicho nodo. Por ejemplo, para una matriz

5   7   7   10
5   2   2   10
4   5   2   6

obtenemos el gráfico conectado:

Donde el nodo 1 es el elemento matriz superior izquierdo y el nodo 12 el elemento inferior derecho. Dadas las coordenadas iniciales p, se calcula la ruta más corta a todos los demás nodos. Entonces, la longitud del camino más largo de esos caminos más cortos + el tiempo para quemar el nodo inicial es igual al tiempo para quemar toda la matriz.

Versión no comentada y comentada con valores iniciales de muestra:

% some starting point
p = [3 2];
% some random 5x6 starting map, integers between 1:10
A = randi(10,5,6); 

function t=F(A,p)
% dimensions of A
[n,m] = size(A);
% create adjacency matrix
x=2:n*m;
x(mod(x,n)==1)=0;
B = diag(x,1)+diag(n+1:n*m,n);
B = B+B';
B = bsxfun(@times,(B~=0),A(:))';
% make graph object with it
G = digraph(B);
% starting node
k = sub2ind([n m], p(1), p(2));
% calculate the shortest distance to all nodes from starting point
d = distances(G,k);
% the largest smallest distance will burn down last. Add burntime of initial point
t = max(d)+A(k);

JavaScript (ES6), 156 152 146 144 143 bytes

Guardado 1 byte gracias a Kevin Cruijssen

Una implementación bastante ingenua. Toma entrada en la sintaxis de curry (a)(s), donde a es una matriz 2D y s es una matriz de dos enteros [ x, y ] que representan las coordenadas basadas en 0 de la posición inicial.

a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

Formateado y comentado

a => s => (                                // given a and s
  g = t => (                               // g = recursive function with t = time counter
    a = a.map((r, y) =>                    // for each row r of the input array:
      r.map((c, x) =>                      //   for each cell c in this row:
        (                                  //     z = function that takes
          z = (h, v) =>                    //         2 signed offsets h and v and checks
            (a[y + ~~v] || [])[x + h] < 1  //         whether the corresponding cell is 0
        )(-1) | z(1) |                     //     test left/right neighbors
        z(0, -1) | z(0, 1) |               //     test top/bottom neighbors
        x + ',' + y == s                   //     test whether c is the starting cell
        && c ?                             //     if at least one test passes and c != 0:
          u = c - 1                        //       decrement the current cell / update u
        :                                  //     else:
          c                                //       let the current cell unchanged
      ),                                   //   end of r.map()
      u = -1                               //   start with u = -1
    ),                                     // end of a.map() --> assign result to a
    ~u ?                                   // if at least one cell was updated:
      g(t + 1)                             //   increment t and do a recursive call
    :                                      // else:
      t                                    //   stop recursion and return t
  )                                        // end of g() definition
)(0)                                       // initial call to g() with t = 0

Casos de prueba

let f =

a=>s=>(g=t=>(a=a.map((r,y)=>r.map((c,x)=>(z=(h,v)=>(a[y+~~v]||[])[x+h]<1)(-1)|z(1)|z(0,-1)|z(0,1)|x+','+y==s&&c?u=c-1:c),u=-1),~u?g(t+1):t))(0)

console.log(f([
  [1,1,1,1,1],
  [1,2,2,2,1],
  [1,2,3,2,1],
  [1,2,2,2,1],
  [1,1,1,1,1]
])([2, 2]))

console.log(f([
  [1,1,1,1,1],
  [1,2,2,2,1],
  [1,2,3,2,1],
  [1,2,2,2,1],
  [1,1,1,1,1]
])([0, 0]))

console.log(f([
  [4,2,5,3],
  [2,2,1,3],
  [1,2,1,1]
])([1, 1]))

Octava, 67 bytes

function n=F(s,a)n=0;do++n;until~(s-=a|=imdilate(~s,~(z=-1:1)|~z')

Pruébalo en línea!

Para visualizar resultados intermedios, ¡puede probar esto!

Una función que toma como matriz de entrada del terreno ay coordenada inicial como una matriz de 0 y 1 con el mismo tamaño que el terreno.

En realidad, no hay necesidad de endfunctionejecutar el ejemplo en tio, debería agregarse.

Explicación:

Aplique repetidamente dilatación de imágenes morfológicas en el terreno y reste las áreas quemadas.

Respuesta sin golf:

function n = Fire(terrain,burned)
    n = 0;
    mask = [...
            0  1  0
            1  1  1
            0  1  0];
    while true
        n = n + 1;
        propagation = imdilate(~terrain, mask);
        burned = burned | propagation;
        terrain = terrain - burned;
        if all(terrain(:) == 0)
            break;
        end
    end
end

MATL , 26 25 bytes

Tenía muchas ganas de ver algunas respuestas más usando los idiomas más modernos por aquí

`yy)qw(8My~1Y6Z+fhy0>z}@&

El formato de entrada es:

• La primera entrada es una matriz que usa ;como separador de filas.

• La segunda entrada es un número único que se dirige a una entrada de la matriz en orden de columna mayor basada en 1 (permitido por el desafío). Por ejemplo, la coordenada principal-columna de cada entrada en una matriz 3 × 4 viene dada por

  1  4  7 10
  2  5  8 11
  3  6  9 12
  

  Entonces, por ejemplo, las coordenadas basadas en 1 (2,2) corresponden 5.

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

El código mantiene una lista de entradas que se están grabando. En cada iteración, todas las entradas de esa lista se reducen. Cuando una entrada llega a cero, sus entradas vecinas se agregan a la lista. Para guardar bytes, las entradas que llegan a cero no se eliminan de la lista; en cambio, siguen "ardiendo" con valores negativos. El ciclo se cierra cuando ninguna de las entradas tiene valores positivos.

Vea el programa que se ejecuta paso a paso con código ligeramente modificado.

Código comentado:

`      % Do...while
  yy   %   Duplicate top two arrays (matrix and array of positions to be decremented)
       %   In the first iteration this implicitly takes the two inputs
  )    %   Reference indexing. This gives the values that need to be decremented
  q    %   Decrement
  w    %   Swap. This brings the array of positions that have been decremented to top
  (    %   Assignment indexing. This writes the decremented values back into their
       %   positions
  8M   %   Push array of positions again
  y    %   Duplicate decremented matrix
  ~    %   Negate. This replaces zeros by 1, and nonzeros by 0
  1Y6  %   Push predefined literal [0 1 0; 1 0 1; 0 1 0] (4-neighbourhood)
  Z+   %   2D convolution, maintaining size
  f    %   Find: gives column-major indices of neighbours of totally burnt entries
  h    %   Concatenate. This updates the array of positions to be decremented
  y    %   Duplicate decremented matrix
  0>   %   This gives 1 for positive entries, and 0 for the rest
  z    %   Number of nonzeros. This is the loop condition (*)
}      % Finally (execute before exiting loop)
  @    %   Push iteration number. This is the output
  &    %   Specify that the final implicit display function will display only the top
       %   of the stack
       % Implicit end. If the top of the stack (*) is not 0 (i.e. there are entries
       % that have not been totally burnt) the loop proceeds with the next iteration.
       % Else the "finally" branch is executed and the loop is exited
       % Implicit display (only top of the stack)

Python 2 , 170 bytes

s,m=input()
t={s}
r=0
while max(sum(m,[]))>0:
 r+=1
 for a,b in t|t:
	try:a<0<x;b<0<x;m[a][b]-=1;t|=m[a][b]==0and{(a+1,b),(a-1,b),(a,b+1),(a,b-1)}or t^t
	except:0
print r

Pruébalo en línea!

Python 3 , 277 266 bytes

def f(m,s):
 p={s};w=len(m);t=0
 while sum(sum(m,[])):
  t+=1;i=0
  for x,y in p:
   try:m[x][y]=max(0,m[x][y]-1)
   except:0
  for v in sum(m,[]):
   if v<1:
    for l in[(1,0),(-1,0),(0,1),(0,-1)]:a,b=max(0,i%w+l[0]),max(0,i//w+l[1]);p.add((a,b))
   i+=1
 print(t)

Pruébalo en línea!

Define una función fque toma una matriz 2D y una tupla de puntos. La primera cosa que la función hace es definir un conjunto de tuplas que contienen el valor tupla inicial aprobada en: p={s}. La función luego pasa por cada tupla de puntos py resta uno de la matriz men ese punto, a menos que el valor ya sea cero. Luego, mvuelve a recorrerlo en busca de todos los puntos con el valor cero y agrega los cuatro vecinos de ese punto al conjunto p. Es por eso que elegí usar un conjunto, porque los conjuntos en Python no permiten valores duplicados (lo que arruinaría mucho la resta). Desafortunadamente, debido al ajuste del índice de la lista (p. Ej . list[-1] == list[len(list)-1]:), los índices deben restringirse para que no se vuelvan negativos y agreguen las coordenadas incorrectas p.

Nada especial, aún acostumbrarse al golf. Definitivamente hay margen de mejora aquí, voy a seguir agrietándolo.

APL (Dyalog) , 93 66 57 bytes

{⍵{^/,0≥⍺:0⋄1+x∇⍵∨{∨/,⍵∧⍲/¨2|⍳3 3}⌺3 3⊢0=x←⍺-⍵}(⊂⍺)≡¨⍳⍴⍵}

Pruébalo en línea!o Visualízalo en línea!

Esta función toma la matriz del terreno como argumento derecho y las coordenadas (basadas en 1) del primer disparo como argumento izquierdo. Devuelve el número de minutos necesarios para grabar todo.

Actualizaciones

Finalmente encontré una manera de jugar golf en la función de propagación.
* Suspiro * sería mucho más fácil si el mundo fuera toroidal .

TIO acaba de actualizar a Dyalog 16.0 , lo que significa que ahora tenemos el nuevo y brillante operador de plantilla

Python 2 , 268 bytes

def f(m,y,x):t,m[y][x]=m[y][x],0;g(m,t)
def g(m,t):
	n,h,w=map(lambda r:r[:],m),len(m),len(m[0])
	for l in range(h*w):r,c=l/h,l%h;n[r][c]-=m[r][c]and not all(m[r][max(c-1,0):min(c+2,w+1)]+[m[max(r-1,0)][c],m[min(r+1,h-1)][c]])
	if sum(sum(m,[])):g(n,t+1)
	else:print t

Pruébalo en línea!

Repetir recursivamente a lo largo del tiempo los pasos en los que se reduce el número de cada mosaico si es cardinalmente adyacente a un 0. Algoritmo muy sencillo que, en mi opinión, todavía se puede jugar para obtener una eficiencia booleana ...

* nota: mi '¡Pruébelo en línea!' el código incluye registro de depuración adicional en el pie de página. Me gusta ver el progreso del algoritmo.

Haskell , 138 133 bytes

u#g|all((<=0).snd)g=0|2>1=1+(u:[[(x+1,y),(x-1,y),(x,y-1),(x,y+1)]|((x,y),0)<-n]>>=id)#n where n=d<$>g;d p|elem(fst p)u=pred<$>p|2>1=p

Pruébalo en línea!

Asume que la entrada es una lista de ((x, y), celda). Sin golf:

type Pos = (Int, Int)

ungolfed :: [Pos] -> [(Pos, Int)] -> Int
ungolfed burning grid
  | all ((<=0).snd) grid = 0 
  | otherwise = 1 + ungolfed (burning ++ newburning) newgrid
 where
  newgrid = map burn grid
  burn (pos,cell) | pos `elem` burning = (pos, cell - 1)
                  | otherwise = (pos, cell)
  newburning = do
    ((x,y),cell) <- newgrid
    guard (cell <= 0)
    [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]