Supposons que nous ayons une matrice comme celle-ci:

11111
12221
12321
12221
11111

Cette matrice représente un terrain et chaque cellule représente une portion de terrain. Le nombre dans chaque cellule représente le temps pendant lequel la portion de terrain doit être complètement brûlée (en minutes, si une unité de mesure est nécessaire), selon sa combustibilité . Si un feu démarre à une position donnée (cellule), cette cellule doit être complètement brûlée avant que le feu ne se propage aux cellules adjacentes (horizontale et verticale uniquement, pas en diagonale). Donc, si un feu est démarré en position centrale, le feu a besoin:

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

Explication:

• Le feu commence à [2,2] (sur la base de 0), ce qui a un temps de combustion de 3.
• Après 3 minutes, [1,2], [2,1], [2,3], [3,2] commencent à brûler.
• Après 2 minutes, ces cellules finissent de brûler et le feu se propage à toutes les cellules adjacentes, mais [0,2], [2,0], [2,4], [0,4] n'ont besoin que d'une minute de plus pour brûler, donc
• Après 1 minute, ces cellules sont brûlées et la cellule se propage aux cellules adjacentes.
• Après 1 minute de plus, le reste des cellules de l'étape 3 finit de brûler et le feu se propage vers leurs cellules adjacentes (qui sont déjà brûlées, donc rien ne se passe).
• Après 1 dernière minute, le feu finit de brûler tout le terrain.

La solution à ce cas est donc de 8 minutes. Si le feu démarre dans la cellule la plus à gauche [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

Alors maintenant, le temps total est de 10 minutes.

Le défi

Étant donné une matrice NxM (N> 0, M> 0) de valeurs entières qui représentent le temps nécessaire à chaque cellule pour être complètement consommée, écrivez le programme / la fonction la plus courte qui prend cette matrice et une paire d'entiers avec la position dans laquelle le feu commence. , et retourne / imprime le temps nécessaire au feu pour consommer complètement le terrain entier.

• Chaque cellule aura un temps de combustion positif (non nul). Vous ne pouvez pas supposer une valeur maximale pour les cellules.
• La matrice n'a pas besoin d'être carrée ni symétrique.
• La matrice peut être indexée 0 ou indexée 1, comme vous le souhaitez.
• La position peut être donnée en tant que paramètre unique avec un tuple d'entiers, deux paramètres distincts de tout autre format raisonnable.
• Les dimensions de la matrice ne peuvent pas être spécifiées comme paramètres d'entrée.
• Vous n'avez pas besoin de sortir chaque étape intermédiaire, juste le temps demandé. Mais je ne me plaindrai pas si les étapes sont visualisées de quelque façon que ce soit.

Un autre exemple:

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

C'est du golf de code , alors le programme le plus court pour chaque langue peut gagner!

Matlab, 235 257 190 182 178 178 octets

Entrée: matrice A, vecteur 1x2 pcontenant les coordonnées de départ.

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)

Explication:

Au lieu de simuler la propagation du feu, nous pouvons également comprendre cela comme un problème de "trouver le chemin le plus long le plus court". La matrice est convertie en un graphique dirigé pondéré. Les poids des chemins vers un seul nœud correspondent au temps de gravure dudit nœud. Par exemple pour une matrice

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

on obtient le graphe connecté:

Où le nœud 1 est l'élément de matrice supérieur gauche et le nœud 12 l'élément inférieur droit. Étant donné les coordonnées de départ p, le chemin le plus court vers tous les autres nœuds est calculé. Ensuite, la longueur du chemin le plus long de ces chemins les plus courts + le temps de graver le nœud initial est égal au temps de graver la matrice entière.

Version non golfée et commentée avec des exemples de valeurs de départ:

% 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 octets

1 octet enregistré grâce à Kevin Cruijssen

Une implémentation plutôt naïve. Prend une entrée dans la syntaxe de curry (a)(s), où a est un tableau 2D et s est un tableau de deux entiers [ x, y ] représentant les coordonnées basées sur 0 de la position de départ.

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)

Formaté et commenté

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

Cas de test

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

Octave, 67 octets

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

Essayez-le en ligne!

Pour visualiser les résultats intermédiaires, vous pouvez essayer ceci!

Une fonction qui prend comme matrice d'entrée du terrain aet les coordonnées initiales comme une matrice de 0 et 1 avec la même taille que le terrain.

En fait, il n'est pas nécessaire endfunctioncependant d'exécuter l'exemple in tio, il doit être ajouté.

Explication:

Appliquer à plusieurs reprises une dilatation morphologique de l'image sur le terrain et en soustraire les zones brûlées.

Réponse non golfée:

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 octets

Je voulais vraiment voir plus de réponses en utilisant les langues les plus golfiques d'ici

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

Le format d'entrée est:

• La première entrée est une matrice utilisant ;comme séparateur de lignes.

• La deuxième entrée est un numéro unique qui adresse une entrée de la matrice dans un ordre de colonne majeur basé sur 1 (autorisé par le défi). Par exemple, la coordonnée colonne-majeure de chaque entrée dans une matrice 3 × 4 est donnée par

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

  Ainsi, par exemple, les coordonnées basées sur 1 (2,2) correspondent à 5.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Le code conserve une liste des entrées en cours de gravure. À chaque itération, toutes les entrées de cette liste sont décrémentées. Lorsqu'une entrée atteint zéro, ses entrées voisines sont ajoutées à la liste. Pour enregistrer des octets, les entrées qui atteignent zéro ne sont pas supprimées de la liste; au lieu de cela, ils continuent de "brûler" avec des valeurs négatives. La boucle est fermée lorsqu'aucune des entrées n'a de valeurs positives.

Voir le programme en cours d'exécution étape par étape avec du code légèrement modifié.

Code commenté:

`      % 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 octets

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

Essayez-le en ligne!

Python 3 , 277 266 octets

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)

Essayez-le en ligne!

Définit une fonction fqui prend une matrice 2D et un tuple de points. La première chose que fait la fonction est de définir un ensemble de tuples contenant la valeur de uplet initial transmis à: p={s}. La fonction passe ensuite par chaque tuple de points dans pet soustrait un de la matrice mà ce point, sauf si la valeur est déjà nulle. Il passe ensuite en revue à mnouveau tous les points avec la valeur zéro et en ajoutant les quatre voisins de ce point à l'ensemble p. C'est pourquoi j'ai choisi d'utiliser un ensemble, car les ensembles en Python n'autorisent pas les valeurs en double (ce qui bousillerait beaucoup la soustraction). Malheureusement, en raison de l'habillage d'index de liste (par exemple list[-1] == list[len(list)-1]:), les indices doivent être contraints afin qu'ils ne deviennent pas négatifs et qu'ils ajoutent les mauvaises coordonnées à p.

Rien de spécial, toujours habitué au golf. Certainement matière à amélioration ici, je vais continuer à le craquer.

APL (Dyalog) , 93 66 57 octets

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

Essayez-le en ligne! ou visualisez-le en ligne!

Cette fonction prend la matrice de terrain comme argument de droite et les coordonnées (basées sur 1) du premier tir comme argument de gauche. Renvoie le nombre de minutes nécessaires pour tout graver.

Mises à jour

Enfin trouvé un moyen de jouer au golf sur la fonction de propagation.
* Soupir * ce serait tellement plus facile si le monde était toroïdal .

TIO vient d'être mis à niveau vers Dyalog 16.0 , ce qui signifie que nous avons maintenant le nouvel opérateur de pochoir brillant

Python 2 , 268 octets

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

Essayez-le en ligne!

Itérer récursivement sur des pas de temps dans lesquels le nombre de chaque tuile est réduit s'il est cardinalement adjacent à un 0. Algorithme très simple qui, je crois, peut encore être joué pour l'efficacité booléenne ...

* remarque: mon "Essayez-le en ligne!" le code inclut la journalisation du débogage bonus dans le pied de page. J'aime regarder la progression de l'algorithme.

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

Essayez-le en ligne!

Suppose que l'entrée est une liste de ((x, y), cellule). Non 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)]