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!
źródło
1
doM*N
Odpowiedzi:
Matlab,
235257190182178 bajtówDane wejściowe: macierz
A
, wektor 1x2p
zawierający współrzędne początkowe.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
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:
źródło
;
po każdej linii. W Matlab zapobiegają one wyświetlaniu wyników każdego polecenia w konsoli. Obecnie kod jest bardzo rozmowny i przekierowuje konsolę. Ale ponieważ nie jest to stan bezwzględnej awarii, utrzymałem go w ten sposób. Ale to nie ma większego znaczenia, to tylko 4 bajtyJavaScript (ES6),
156152146144143 bajtówZaoszczę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.Sformatowane i skomentowane
Przypadki testowe
Pokaż fragment kodu
źródło
==0
można grać w golfa,<1
jeśli się nie mylę.undefined<1
fałsz. Dzięki!Oktawa, 67 bajtów
Wypróbuj online!
Aby wizualizować wyniki pośrednie, możesz wypróbować to!
Funkcja, która przyjmuje jako macierz wejściową terenu
a
i współrzędną początkową jako macierz 0 i 1 o tym samym rozmiarze co teren.W rzeczywistości nie trzeba
endfunction
jednak 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:
źródło
n=1
nan=0
.MATL ,
2625 bajtówFormat 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
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:
źródło
Python 2 , 170 bajtów
Wypróbuj online!
źródło
Python 3 ,
277266 bajtówWypróbuj online!
Definiuje funkcję,
f
któ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ówp
i odejmuje jeden od macierzym
w tym punkcie, chyba że wartość jest już równa zero. Następnie przechodzi przez pętlęm
ponownie, znajdując wszystkie punkty o wartości zero i dodając czterech sąsiadów tego punktu do zbiorup
. 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 (nplist[-1] == list[len(list)-1]
.:) indeksy muszą być ograniczone, aby nie były ujemne i dodawały niewłaściwe współrzędnep
.Nic specjalnego, wciąż przyzwyczajającego się do gry w golfa. Zdecydowanie tu jest miejsce na ulepszenia, zamierzam nadal to robić.
źródło
APL (Dyalog) ,
936657 bajtówWypró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
źródło
Python 2 , 268 bajtów
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.
źródło
Haskell ,
138133 bajtówWypróbuj online!
Zakłada, że dane wejściowe to lista ((x, y), komórka). Nie golfowany:
źródło