Berechnen Sie die 3BV eines Minesweeper Boards

17

Das 3BV eines Minesweeper- Boards gibt die minimale Anzahl von Linksklicks an, die erforderlich sind, um das Board zu lösen, wenn Sie die Lösung bereits kennen. Es steht für "Bechtel's Board Benchmark Value". Hier ist seine Seite , die es erklärt.

Unten ist ein gelöstes Minesweeper-Board. Die Flaggen zeigen Minen an; Kacheln ohne Minen geben die Anzahl benachbarter Minen an, auch diagonal, mit der Ausnahme, dass Kacheln mit "0" leer bleiben. Das Bild zeigt, welche Kacheln angeklickt werden müssen, um das Brett zu lösen.

3BV zählen

Für die 3BV gezählte Klicks sind:

  • Eine für jeden überfluteten Bereich mit leeren Kacheln (null Minen nebeneinander) und deren nicht leeren Nachbarn.
  • Eine für jede andere Nicht-Minen-Fliese.

Ein weiteres Beispiel (3BV = 39)

Gelöstes Minensuchbrett Klicks erforderlich


Bei einem gegebenen 2D-Array von Werten geben Sie 0für clear und 1für eine Mine (oder einen Booleschen Wert ) die 3BV zurück .

Die Abmessungen eines Boards betragen mindestens 8x8 und höchstens 24x30. Ihr Programm sollte alle möglichen Karten verarbeiten, nicht nur die Beispiele.

Hinweis: Ein Brett enthält niemals nur Minen.

Beispiel 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
mbomb007
quelle
Ist ein Array von Ganzzahlen als Eingabe in Ordnung? Jede Ganzzahl codiert eine Zeile.
Karl Napf
@KarlNapf Nein. Der Eingang sollte wie abgebildet als Platine erkennbar sein.
mbomb007
Könnten Sie mehr Testfälle bereitstellen, möglicherweise einschließlich der Eingabe basierend auf den angezeigten Bildern, und möglicherweise einen Testfall mit maximalen Abmessungen?
Meilen

Antworten:

15

MATLAB, 92 90 86 83 79 74 72 Bytes

x=input('');I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N

Diese Lösung akzeptiert die Eingabe in Form einer 2D-Matrix aus Nullen und Einsen und zeigt den 3BV-Wert für die bereitgestellte Eingabe an.

Hier ist eine leicht modifizierte Demo in Octave für diejenigen unter Ihnen ohne MATLAB.

Erläuterung

Die Eingabematrix wird mit einer 3 x 3-Matrix von 1's erweitert und dann invertiert (using ~), wodurch alle Punkte identifiziert werden, die keine Minen als Nachbarn haben ( 1) oder do ( 0). Um die Anzahl der verbundenen Regionen zu bestimmen, kennzeichnen wir bwlabeljede verbundene Region von 1. Die erste Ausgabe ist die Beschriftungsmatrix ( 0wobei die Eingabe Null war und ein beliebiger Wert in dem Bereich, 1...Nin dem sich eine 1Eingabe befand, in dem Nsich der Index der verbundenen Gruppe befindet, zu der sie gehört). Die zweite Ausgabe ist die Anzahl der Regionen (die Anzahl der Klicks, die erforderlich sind, um sie zu öffnen). Das Ergebnis von bwlabelwird im Bild links angezeigt.

Bildbeschreibung hier eingeben

Wir erweitern die erste Ausgabe von bwlabelusing imdilate(alle Nicht-Nullen werden erweitert) mit einer 3 x 3-Matrix von 1's. Das Ergebnis ist in der Abbildung in der Mitte dargestellt.

Um die verbleibenden Klicks zu bestimmen, zählen wir die Quadrate, die sich nicht in diesem erweiterten Bereich ( ~imdilate()) und nicht in einer Mine ( -x) befinden (weiße Quadrate im Bild rechts) und addieren diese zur Gesamtzahl der offenen Bereiche (die Anzahl der) verschiedene Farben im Bild links), um die 3BV zu erhalten.

Suever
quelle
9

Oktave, 86 84 79 66 Bytes

@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:))

Diese Lösung erstellt eine anonyme Funktion mit dem Namen, ansder dann eine 2D-Matrix von 0's und 1' s übergeben werden kann. Die Logik ist dieselbe wie bei meiner MATLAB-Antwort, verwendet jedoch einige Tricks, die Octave zu bieten hat, um Platz zu sparen.

Diese Lösung setzt voraus, dass das imagePaket installiert ist.

Demo hier

Suever
quelle
2

MATL, 24 22 21 Bytes (nicht konkurrierend)

1 Byte gespart dank @Luis

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

Probieren Sie es bei MATL Online aus

Erläuterung

Auch dies ähnelt den Antworten von MATLAB und Octave auf diese Frage.

        % 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 
Suever
quelle
Warum nicht konkurrieren?
CalculatorFeline
1
@CalculatorFeline Leider wurde die bwlabelnFunktionalität in MATL eingeführt, nachdem die Herausforderung veröffentlicht wurde.
Suever