3BV for en Minestryger -kortet repræsenterer det mindste antal venstre klik, der kræves for at løse kortet, hvis du allerede kender løsningen. Det står for ” Bechtels Board Benchmark Value “. Her “s hans site , der forklarer det.
Nedenfor er et løst Minesweeper board. Flagene angiver miner; fliser uden miner angiver antallet af tilstødende miner, inklusive diagonalt, bortset fra at fliser, der skal have ” 0 “, bliver i stedet tomme. Billedet viser, hvilke fliser der skal klikkes for at løse brættet.
Klik tælles mod 3BV er:
- Ét for hvert oversvømmelsesfyldte område blanke fliser (nul miner tilstødende) og deres ikke-blanke naboer.
- En til hinanden ikke-minefliser.
Et andet eksempel (3BV = 39)
Givet et 2D-array af værdier, 0 for klar og 1 for en mine (eller en boolsk), returnerer 3BV .
Dimensionerne på et kort vil være mindst 8×8 og højst 2 4×30 inklusive. Dit program skal håndtere alle mulige tavler, ikke kun eksemplerne.
Bemærk: Et tavle indeholder aldrig kun miner.
Eksempel 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
- Er en række heltal okay som input? Hvert heltal koder en række.
- @KarlNapf Nej. Indgangen skal kunne genkendes som et kort som vist.
- Kan du give flere testtilfælde, muligvis inklusive input baseret på det viste billeder, og måske et testmål med maks. dimensioner?
Svar
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 Denne løsning accepterer input i form af en 2D-matrix på 0 “s og 1” s og viser 3BV-værdien for den leverede input.
Her er lidt ændret demo i oktav for jer uden MATLAB.
Forklaring
Inputmatricen er udvidet ved hjælp af en 3 x 3 matrix af 1 “s og derefter inverteret (ved hjælp af ~), som identificerer alle de punkter, der ikke har miner som naboer (1) eller gør (). For at bestemme antallet af tilsluttede regioner bruger vi bwlabel til at mærke hver tilsluttet region af 1 “s. Den første output er etiketmatricen (0 hvor input var nul og enhver værdi i området 1...N hvor der var en 1 i input, hvor N er indekset for den tilsluttede gruppe, som den tilhører). Den anden output er antallet af regioner (antallet af klik, der kræves for at åbne dem). Resultatet af bwlabel vises på billedet til venstre.
Vi udvider den første output af bwlabel ved hjælp af imdilate (alle ikke-nuller udvides) ved hjælp af en 3 x 3 matrix af 1 “s. Resultatet vises på billedet i midten.
For at bestemme de resterende klik tæller vi derefter de firkanter, der ikke er i dette udvidede område (~imdilate()) og ikke en mine (-x) (hvide firkanter i billedet til højre) og tilføj dette til det samlede antal åbne regioner (antallet af forskellige farver i billedet til venstre ) for at få 3BV.
Svar
Oktav, 86 84 79 66 byte
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Denne løsning opretter en anonym funktion ved navn ans kan derefter sendes en 2D-matrix af 0 “s og 1” s. Logikken er den samme som mit MATLAB-svar, men bruger et par tricks, som Octave har at tilbyde for at spare plads.
Denne løsning kræver, at pakken image er installeret .
Svar
MATL, 24 22 21 bytes (ikke-konkurrerende )
1 byte gemt takket være @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Prøv det på MATL Online
Forklaring
Igen svarer dette til mine MATLAB- og Octave-svar på dette spørgsmål.
% 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
- Ikke-konkurrerende hvorfor?
- @CalculatorFeline Desværre blev
bwlabeln-funktionen introduceret til MATL efter udfordring blev sendt.