Die 3BV einer Minesweeper Board gibt die Mindestanzahl von Linksklicks an, die zum Lösen des Boards erforderlich sind, wenn Sie die Lösung bereits kennen. Es steht für “ Bechtels Board Benchmark Value „. Hier ist his Seite erklärt es.
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 “ stattdessen leer bleiben. Das Bild zeigt, auf welche Kacheln geklickt werden muss, um das Board zu lösen.
Für die 3BV gezählte Klicks sind:
- Eine für jeden mit Überschwemmungen gefüllten Bereich von leeren Kacheln (keine Minen nebeneinander) und ihren nicht leeren Nachbarn.
- Eine für jede andere Nicht-Minen-Kachel.
Ein weiteres Beispiel (3BV = 39)
Bei einem 2D-Array von Werten ist 0 für clear und 1 für eine Mine (oder einen Booleschen Wert), gibt die 3BV .
Die Abmessungen einer Platine betragen mindestens 8 x 8 und höchstens 2 4×30 inklusive. Ihr Programm sollte alle möglichen Karten behandeln, nicht nur die Beispiele.
Hinweis: Eine Karte enthält niemals nur Minen.
Beispiel-E / A:
[[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 Kommentare
- Ist ein Array von Ganzzahlen als Eingabe in Ordnung? Jede Ganzzahl codiert eine Zeile.
- @KarlNapf Nein. Die Eingabe sollte wie gezeigt als Karte erkennbar sein.
- Könnten Sie weitere Testfälle bereitstellen, möglicherweise einschließlich der Eingabe basierend auf der angezeigten Bilder und möglicherweise ein Testfall mit maximalen Abmessungen?
Antwort
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 von 0 „s und 1“ s 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 unter Verwendung einer 3 x 3-Matrix von 1 „erweitert und dann invertiert (mit ~), das alle Punkte identifiziert, die keine Minen haben, als Nachbarn (1) oder do (). Um die Anzahl der verbundenen Regionen zu bestimmen, verwenden wir bwlabel, um jede verbundene Region von 1 zu kennzeichnen. Die erste Ausgabe ist die Beschriftungsmatrix (0 wobei die Eingabe Null war und ein beliebiger Wert im Bereich 1...N wo es eine 1 in der Eingabe, wobei N der Index der verbundenen Gruppe ist, zu der sie gehört). Die zweite Ausgabe ist die Anzahl der Regionen (die Anzahl der Klicks, die zum Öffnen erforderlich sind). Das Ergebnis von bwlabel wird im Bild links angezeigt.
Wir erweitern die erste Ausgabe von bwlabel mit imdilate (alle Nicht-Nullen werden erweitert) unter Verwendung einer 3 x 3-Matrix von 1 „s. Das Ergebnis wird im Bild in der Mitte angezeigt.
Um die verbleibenden Klicks zu ermitteln, zählen wir die Quadrate, die sich nicht in diesem erweiterten Bereich befinden (~imdilate()). und keine Mine (-x) (weiße Quadrate im Bild rechts) und addieren Sie diese zur Gesamtzahl der offenen Bereiche (die Anzahl der verschiedenen Farben im Bild links) ), um die 3BV zu erhalten.
Antwort
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 ans kann dann eine 2D-Matrix von 0 „s und 1“ s übergeben werden. Die Logik ist dieselbe wie meine MATLAB-Antwort, verwendet jedoch einige Tricks, die Octave bietet, um Platz zu sparen.
Für diese Lösung muss das Paket image installiert sein .
Antwort
MATL, 24 22 21 Bytes (nicht konkurrierend) )
1 Byte dank @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Versuchen Sie es unter MATL Online
Erläuterung
Auch dies ähnelt meinen MATLAB- und Octave-Antworten 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 Kommentare
- Warum nicht konkurrieren?
- @CalculatorFeline Leider wurde die
bwlabeln-Funktionalität in MATL nach dem eingeführt Herausforderung wurde veröffentlicht.