3BV för en Minesweeper -kortet representerar det minsta antal vänsterklick som krävs för att lösa kortet om du redan känner till lösningen. Det står för ” Bechtels Board Benchmark Value ”. Här ”s hans webbplats som förklarar det.
Nedan finns ett löst Minesweeper-kort. Flaggorna indikerar gruvor; brickor utan gruvor anger antalet angränsande gruvor, inklusive diagonalt, förutom att brickor som ska ha ” 0 ” lämnas tomma istället. Bilden visar vilka brickor som behöver klickas för att lösa kortet.
Klick som räknas mot 3BV är:
- En för varje översvämningsfylld område av tomma brickor (noll gruvor intill) och deras icke-tomma grannar.
- En för varandra icke-gruvan.
Ett annat exempel (3BV = 39)
Med tanke på en 2D-array med värden, 0 för tydlig och 1 för en gruva (eller en boolean), returnera 3BV .
Ett kortets mått kommer att vara minst 8×8 och högst 2 4×30, inklusive. Ditt program ska hantera alla möjliga tavlor, inte bara exemplen.
Obs! En tavla innehåller aldrig bara gruvor.
Exempel 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 Kommentarer
- Är en rad heltal okej som inmatning? Varje heltal kodar en rad.
- @KarlNapf Nej. Ingången ska kännas igen som en tavla som visas.
- Kan du ge fler testfall, eventuellt inklusive inmatningen baserat på den visade bilder och kanske ett testfall med max dimensioner?
Svar
MATLAB, 92 90 86 83 79 74 72 byte
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N Denna lösning accepterar ingången i form av en 2D-matris på 0 ”s och 1” s och visar 3BV-värdet för den angivna ingången.
Här är något ändrad demo i Oktav för er utan MATLAB.
Förklaring
Ingångsmatrisen utvidgas med en 3 x 3 matris av 1 ”s och sedan inverteras (med ~) som identifierar alla punkter som inte har gruvor som grannar (1) eller gör (). För att bestämma antalet anslutna regioner använder vi bwlabel för att märka varje ansluten region av 1 ”s. Den första utmatningen är etikettmatrisen (0 där ingången var noll och något värde i intervallet 1...N där det fanns en 1 i ingången där N är indexet för den anslutna gruppen som den tillhör). Den andra utgången är antalet regioner (antalet klick som krävs för att öppna dem). Resultatet av bwlabel visas på bilden till vänster.
Vi utökar den första utgången av bwlabel med imdilate (alla icke-nollor utvidgas) med en 3 x 3 matris av 1 ”s. Resultatet visas i bilden i mitten.
För att bestämma återstående klick räknar vi sedan rutorna som inte finns i det utvidgade området (~imdilate()) och inte en gruva (-x) (vita rutor i bilden till höger) och lägg till detta till det totala antalet öppna regioner (antalet olika färger i bilden till vänster ) för att få 3BV.
Svar
Oktav, 86 84 79 66 byte
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Denna lösning skapar en anonym funktion med namnet ans kan sedan skickas en 2D-matris med 0 ”s och 1” s. Logiken är densamma som mitt MATLAB-svar men använder några knep som Octave har att erbjuda för att spara utrymme.
Denna lösning kräver att paketet image är installerat .
Svar
MATL, 24 22 21 byte (icke-konkurrerande )
1 byte sparad tack vare @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Prova på MATL Online
Förklaring
Återigen, det här liknar mina MATLAB- och Octave-svar på denna fråga.
% 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 Kommentarer
- Icke-konkurrerande varför?
- @CalculatorFeline Tyvärr introducerades
bwlabeln-funktionen till MATL efter utmaningen publicerades.