Załóżmy, że mamy taką macierz:

11111
12221
12321
12221
11111

Ta matryca reprezentuje teren, a każda komórka reprezentuje część terenu. Liczba w każdej komórce reprezentuje czas, w którym część terenu musi zostać całkowicie spalona (w minutach, jeśli potrzebna jest jednostka miary), zgodnie z jej palnością . Jeśli ogień rozpocznie się w dowolnej pozycji (komórce), komórka ta musi zostać całkowicie spalona, ​​zanim ogień rozprzestrzeni się na sąsiednie komórki (tylko poziomo i pionowo, a nie po przekątnej). Tak więc, jeśli pożar zostanie rozpoczęty w pozycji środkowej, ogień potrzebuje:

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

Wyjaśnienie:

• Ogień rozpoczyna się w [2,2] (w oparciu o 0), który ma czas spalania 3.
• Po 3 minutach [1,2], [2,1], [2,3], [3,2] zaczynają się palić.
• Po 2 minutach komórki te kończą palenie, a ogień rozprzestrzenia się na wszystkie sąsiednie komórki, ale [0,2], [2,0], [2,4], [0,4] potrzebują tylko 1 minuty, aby spalić, więc
• Po 1 minucie komórki te są spalane, a komórka propaguje się do sąsiednich komórek.
• Po 1 minucie pozostałe komórki z etapu 3 kończą palenie, a ogień rozprzestrzenia się na sąsiednie komórki (które są już spalone, więc nic się nie dzieje).
• Po 1 ostatniej minucie ogień kończy się, paląc cały teren.

Rozwiązaniem tej sprawy jest 8 minut. Jeśli pożar rozpocznie się w górnej lewej komórce [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

Zatem teraz całkowity czas wynosi 10 minut.

Wyzwanie

Biorąc pod uwagę macierz NxM (N> 0, M> 0) wartości całkowitych, które reprezentują czas, w którym każda komórka musi zostać całkowicie zużyta, napisz najkrótszy program / funkcję, która przyjmuje tę macierz i parę liczb całkowitych z pozycją, w której rozpoczyna się ogień , i zwraca / drukuje czas potrzebny do całkowitego pożaru całego terenu.

• Każda komórka będzie miała dodatni (niezerowy) czas spalania. Nie można przyjąć maksymalnej wartości dla komórek.
• Matryca nie musi być kwadratowa ani symetryczna.
• Macierz może być dowolnie indeksowana lub indeksowana 1.
• Pozycja może być podana jako pojedynczy parametr z krotką liczb całkowitych, dwoma oddzielnymi parametrami o dowolnym innym rozsądnym formacie.
• Wymiary matrycy nie mogą być określone jako parametry wejściowe.
• Nie musisz generować każdego pośredniego kroku, wystarczy ilość zadanego czasu. Ale nie będę narzekać, jeśli kroki zostaną w jakikolwiek sposób zwizualizowane.

Inny przykład:

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

To jest golf golfowy , więc może wygrać najkrótszy program dla każdego języka!

Matlab, 235 257 190 182 178 bajtów

Dane wejściowe: macierz A, wektor 1x2 pzawierający współrzędne początkowe.

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)

Wyjaśnienie:

Zamiast symulować rozprzestrzenianie się ognia, możemy to również rozumieć jako problem „znajdź najdłuższą najkrótszą ścieżkę”. Matryca jest konwertowana na ważony ukierunkowany wykres. Wagi ścieżek do pojedynczego węzła odpowiadają czasowi spalenia wspomnianego węzła. Np. Dla matrycy

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

otrzymujemy połączony wykres:

Gdzie węzeł 1 jest lewym górnym elementem matrycy, a węzeł 12 prawym dolnym elementem. Biorąc pod uwagę współrzędne początkowe p, obliczana jest najkrótsza ścieżka do wszystkich innych węzłów. Następnie długość najdłuższej ścieżki tych najkrótszych ścieżek + czas wypalenia węzła początkowego jest równy czasowi wypalenia całej macierzy.

Wersja nieposortowana i skomentowana z przykładowymi wartościami początkowymi:

% 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 bajtów

Zaoszczędził 1 bajt dzięki Kevinowi Cruijssenowi

Raczej naiwne wdrożenie. Pobiera dane wejściowe w składni curry (a)(s), gdzie a jest tablicą 2D, a s jest tablicą dwóch liczb całkowitych [ x, y ] reprezentujących współrzędne 0 pozycji początkowej.

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)

Sformatowane i skomentowane

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

Przypadki testowe

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

Oktawa, 67 bajtów

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

Wypróbuj online!

Aby wizualizować wyniki pośrednie, możesz wypróbować to!

Funkcja, która przyjmuje jako macierz wejściową terenu ai współrzędną początkową jako macierz 0 i 1 o tym samym rozmiarze co teren.

W rzeczywistości nie trzeba endfunctionjednak uruchamiać przykładu in tio, należy go dodać.

Wyjaśnienie:

Wielokrotnie stosuj morfologiczną dylatację obrazu na terenie i odejmuj od niego spalone obszary.

Odpowiedź bez golfa:

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 bajtów

Naprawdę chciałem zobaczyć więcej odpowiedzi w najbardziej golfowych językach tutaj

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

Format wejściowy to:

• Pierwszym wejściem jest macierz używana ;jako separator wierszy.

• Drugie dane wejściowe to pojedyncza liczba, która odnosi się do wpisu macierzy w kolejności 1 -głównej kolumny (dozwolone przez wyzwanie). Na przykład współrzędną główną kolumny dla każdego wpisu w macierzy 3 × 4 podano przez

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

  Na przykład współrzędne 1 (2,2) odpowiadają 5.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Kod utrzymuje listę płonących wpisów. Przy każdej iteracji wszystkie wpisy na tej liście są zmniejszane. Kiedy pozycja osiągnie zero, sąsiednie wpisy zostaną dodane do listy. Aby zapisać bajty, wpisy, które osiągają zero, nie są usuwane z listy; zamiast tego „płoną” z wartościami ujemnymi. Pętla kończy się, gdy żaden z wpisów nie ma dodatnich wartości.

Zobacz program uruchomiony krok po kroku z nieznacznie zmodyfikowanym kodem.

Skomentowany kod:

`      % 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 bajtów

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

Wypróbuj online!

Python 3 , 277 266 bajtów

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)

Wypróbuj online!

Definiuje funkcję, fktóra pobiera macierz 2D i krotkę punktów. Pierwszą rzeczą, funkcja robi to zdefiniować zestaw krotek zawierających wartość początkową krotny przeszedł w: p={s}. Następnie funkcja przechodzi przez każdą krotkę punktów pi odejmuje jeden od macierzy mw tym punkcie, chyba że wartość jest już równa zero. Następnie przechodzi przez pętlę mponownie, znajdując wszystkie punkty o wartości zero i dodając czterech sąsiadów tego punktu do zbioru p. Właśnie dlatego zdecydowałem się użyć zestawu, ponieważ zestawy w Pythonie nie zezwalają na powielanie wartości (co bardzo by popsuło odejmowanie). Niestety, ze względu na zawijanie indeksu listy (np list[-1] == list[len(list)-1].:) indeksy muszą być ograniczone, aby nie były ujemne i dodawały niewłaściwe współrzędne p.

Nic specjalnego, wciąż przyzwyczajającego się do gry w golfa. Zdecydowanie tu jest miejsce na ulepszenia, zamierzam nadal to robić.

APL (Dyalog) , 93 66 57 bajtów

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

Wypróbuj online! lub Wizualizuj to online!

Ta funkcja przyjmuje macierz terenu za prawy argument, a współrzędne (na podstawie 1) pierwszego strzału za lewy argument. Zwraca liczbę minut potrzebną do spalenia wszystkiego.

Aktualizacje

Wreszcie znalazłem sposób na grę w golfa w dół funkcji rozprzestrzeniania.
* Westchnienie * byłoby o wiele łatwiej, gdyby świat był toroidalny .

Właśnie zaktualizowano TIO do Dyalog 16.0 , co oznacza, że ​​teraz mamy nowy błyszczący operator szablonu

Python 2 , 268 bajtów

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

Wypróbuj online!

Rekurencyjnie iteruj w czasie, w którym liczba każdego kafelka jest zmniejszana, jeśli jest on kardynalnie przylegający do 0. Bardzo prosty algorytm, który, jak sądzę, nadal można grać w golfa dla wydajności logicznej ...

* Uwaga: moje „Wypróbuj online!” kod zawiera dodatkowe logowanie do debugowania w stopce. Lubię oglądać postęp algorytmu.

Haskell , 138 133 bajtów

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

Wypróbuj online!

Zakłada, że ​​dane wejściowe to lista ((x, y), komórka). Nie golfowany:

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