3BV Saper przedstawia minimalną liczbę kliknięć lewym przyciskiem potrzebną do rozwiązania planszy, jeśli znasz już rozwiązanie. To oznacza ” Bechtel „s Board Benchmark Value „. Tutaj” s jego strona wyjaśniająca to.
Poniżej znajduje się rozwiązana plansza Saper. Flagi wskazują miny; kafelki bez min wskazują liczbę sąsiadujących min, w tym po przekątnej, z tym wyjątkiem, że kafelki, które powinny mieć ” 0 „, są zamiast tego puste. Obraz pokazuje, które płytki należy kliknąć, aby rozwiązać planszę.
Kliknięcia zaliczane do 3BV to:
- Po jednym na każdy zalany obszar pustych kafelków (zero sąsiadujących min) i ich niepustych sąsiadów.
- Jeden dla siebie kafelek inny niż mój.
Inny przykład (3BV = 39)
Biorąc pod uwagę tablicę wartości 2D, 0 for clear i 1 dla miny (lub boolean), zwróć 3BV .
Tablica ma wymiary co najmniej 8×8, a najwyżej 2 4×30 włącznie. Twój program powinien obsługiwać wszystkie możliwe tablice, a nie tylko przykłady.
Uwaga: tablica nigdy nie będzie zawierała tylko min.
Przykładowe I / O:
[[0,0,0,0,0,0,0,0], [0,0,0,1,0,0,0,0], [0,0,0,1,0,0,1,0], [0,1,0,0,1,0,0,0], [0,0,1,0,0,0,0,1], [0,0,0,1,0,0,0,0], [0,0,0,0,0,0,1,0], [0,0,0,0,0,0,0,1]] 23 [[0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0], [0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0], [0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,0,1,0], [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0], [0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1], [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0], [0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0], [0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0], [1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1], [0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0], [0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,1,1,0,0], [0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0], [0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0], [0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0]] 187 Komentarze
- Czy tablica liczb całkowitych jest w porządku jako dane wejściowe? Każda liczba całkowita koduje jeden wiersz.
- @KarlNapf Nie. Dane wejściowe powinny być rozpoznawalne jako tablica, jak pokazano.
- Czy możesz podać więcej przypadków testowych, prawdopodobnie włączając dane wejściowe oparte na wyświetlanym obrazy, a może przypadek testowy maksymalnych wymiarów?
Odpowiedź
MATLAB, 92 90 86 83 79 74 72 bajty
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N To rozwiązanie akceptuje dane wejściowe w postaci macierzy 2D o wymiarach 0 „si 1” si wyświetli wartość 3BV dla podanego wejścia.
Oto nieco zmodyfikowane demo w Octave dla tych z Was, którzy nie korzystają z MATLAB-a.
Wyjaśnienie
Macierz wejściowa jest rozszerzana za pomocą macierzy 3 x 3 1 „s, a następnie odwracana (przy użyciu ~), który identyfikuje wszystkie punkty, które nie mają min, jako sąsiadów (1) lub do (). Aby określić liczbę połączonych regionów, używamy bwlabel do oznaczenia każdego połączonego regionu 1 „. Pierwszym wynikiem jest macierz etykiet (0 gdzie wartość wejściowa wynosiła zero i dowolna wartość z zakresu 1...N, gdzie występuje 1 na wejściu, gdzie N jest indeksem połączonej grupy, do której należy). Drugim wynikiem jest liczba regionów (liczba kliknięć potrzebna do ich otwarcia). Wynik bwlabel jest pokazany na obrazku po lewej stronie.
Rozwijamy pierwsze wyjście bwlabel za pomocą imdilate (wszystkie niezerowe są interpretowane) przy użyciu macierzy 3 x 3 1 „s. Wynik jest pokazany na obrazku pośrodku.
Aby określić pozostałe kliknięcia, liczymy następnie kwadraty, które nie znajdują się w tym rozwiniętym regionie (~imdilate()) a nie minę (-x) (białe kwadraty na obrazku po prawej stronie) i dodaj to do całkowitej liczby otwartych obszarów (liczba różnych kolorów na obrazku po lewej ), aby uzyskać 3BV.
Odpowiedź
Octave, 86 84 79 66 bajtów
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) To rozwiązanie tworzy anonimową funkcję o nazwie ans, która można następnie przekazać macierz 2D 0 „s i 1” s. Logika jest taka sama jak moja odpowiedź MATLAB, ale wykorzystuje kilka sztuczek, które Octave ma do zaoferowania, aby zaoszczędzić miejsce.
To rozwiązanie wymaga zainstalowania pakietu image .
Odpowiedź
MATL, 24 22 21 bajtów (niekonkurujące )
1 bajt zapisany dzięki @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Wypróbuj na MATL Online
Wyjaśnienie
Ponownie, jest to podobne do moich odpowiedzi w MATLAB-ie i Octave na to pytanie.
% Implicitly grab input array 4Y6 % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack Z+ % Perform 2D convolution of the input with this array ~ % Negate the result l2#ZI % Call bwlabeln which dilates each open region and the second output % returns the number of open regions w % Flip the top two stack elements 7M % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack again Z+ % Perform 2D convolution G+ % Explicitly grab the input and add it to the result ~z % Count the number of 0"s in the result (the remaining number of clicks) + % Add the total number of remaining clicks to the number of open regions Komentarze
- Brak konkurencji, dlaczego?
- @CalculatorFeline Niestety funkcja
bwlabelnzostała wprowadzona do MATL po wyzwanie zostało wysłane.