3BV z Saper pokładzie oznacza minimalną liczbę lewych kliknięć potrzebnych do rozwiązania płytę jeśli już zna rozwiązanie. To skrót od „Bechtel's Board Benchmark Value”. Oto 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”, pozostawiają puste. Obraz pokazuje, które płytki należy kliknąć, aby rozwiązać planszę.

Kliknięcia liczone do 3BV to:

• Jeden na każdy wypełniony powodzią obszar pustych kafelków (sąsiadujących ze sobą min) i ich niepustych sąsiadów.
• Jeden dla siebie inny niż kopalnia.

Kolejny przykład (3BV = 39)

Biorąc pod uwagę tablicę wartości 2D, 0dla wyczyszczenia i 1dla kopalni (lub logicznej), zwróć 3BV .

Wymiary planszy będą wynosić co najmniej 8 x 8, a co najwyżej 24 x 30 włącznie. Twój program powinien obsłużyć wszystkie możliwe tablice, a nie tylko przykłady.

Uwaga: na planszy nigdy nie będą znajdować się tylko miny.

Przykład 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

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 zer i jedynek i wyświetla wartość 3BV dla podanego sygnału wejściowego.

Oto nieco zmodyfikowane demo w Octave dla tych z was, którzy nie mają MATLAB-a.

Wyjaśnienie

Macierz wejściowa jest rozszerzana za pomocą macierzy 3 x 3, 1a następnie odwrócona (za pomocą ~), która identyfikuje wszystkie punkty, które nie mają min, jako sąsiadów ( 1) lub do ( 0). Aby określić liczbę połączonych regionów, używamy bwlabeldo oznaczenia każdego połączonego regionu 1. Pierwszym wyjściem jest matryca etykiet ( 0gdzie wejście było zerowe i dowolna wartość w zakresie, w 1...Nktórym było 1wejście, gdzie Njest indeks połączonej grupy, do której należy). Drugi wynik to liczba regionów (liczba kliknięć wymaganych do ich otwarcia). Wynik bwlabeljest pokazany na obrazku po lewej stronie.

Rozszerzamy pierwszy wynik bwlabelużycia imdilate(wszystkie niezerowe są rozwijane) przy użyciu macierzy 3 x 3 1. Wynik jest pokazany na obrazku pośrodku.

Aby określić pozostałe kliknięcia, zliczamy kwadraty, które nie znajdują się w tym rozwiniętym regionie ( ~imdilate()), a nie kopalni ( -x) (białe kwadraty na obrazie po prawej stronie) i dodajemy to do całkowitej liczby otwartych regionów (liczby różne kolory na obrazku po lewej), aby uzyskać 3BV.

Oktawa, 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, ansktórą można następnie przekazać macierz 2D z 0i 1. Logika jest taka sama jak w mojej odpowiedzi MATLAB, ale wykorzystuje kilka sztuczek, które Octave ma do zaoferowania, aby zaoszczędzić miejsce.

To rozwiązanie wymaga imagezainstalowania pakietu.

Demo tutaj

MATL, 24 22 21 bajtów (niekonkurencyjny)

1 bajt zapisany dzięki @Luis

4Y6Z+~l2#ZIw7MZ+G+~z+

Wypróbuj w MATL Online

Wyjaśnienie

Ponownie, jest to podobne do moich odpowiedzi MATLAB 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