3BV for en Minesveiper -tavle representerer det minste antallet venstre klikk som kreves for å løse tavlen hvis du allerede kjenner løsningen. Det står for » Bechtels Board Benchmark Value «. Her «s hans nettsted som forklarer det.
Nedenfor er et løst Minesveiper-bord. Flaggene indikerer gruver; fliser uten gruver angir antallet tilstøtende miner, inkludert diagonalt, bortsett fra at fliser som skal ha » 0 «, blir stående tomme. Bildet viser hvilke fliser som må klikkes for å løse brettet.
Klikk som telles mot 3BV er:
- Én for hvert flomfylte område blanke fliser (null miner ved siden av) og deres ikke-blanke naboer.
- En for hverandre, ikke-minefliser.
Et annet eksempel (3BV = 39)
Gitt et 2D-utvalg av verdier, 0 for klar og 1 for en gruve (eller en boolsk), returnerer 3BV .
Dimensjoner på et kort vil være minst 8×8 og maksimalt 2 4×30, inkludert. Programmet ditt skal håndtere alle mulige tavler, ikke bare eksemplene.
Merk: Et tavle inneholder aldri bare 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 rekke heltall ok som input? Hvert heltall koder en rad.
- @KarlNapf No. Inngangene skal kunne gjenkjennes som et kort som vist.
- Kan du gi flere testtilfeller, muligens inkludert inndata basert på det viste bilder, og kanskje et testmål med maks dimensjoner?
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 Denne løsningen aksepterer inngangen i form av en 2D-matrise på 0 «s og 1» s og viser 3BV-verdien for den angitte inngangen.
Her er litt modifisert demo i Oktav for de av dere uten MATLAB.
Forklaring
Inngangsmatrisen utvides med en 3 x 3 matrise av 1 «s og deretter inverteres (ved hjelp av ~) som identifiserer alle punktene som ikke har miner som naboer (1) eller gjør (). For å bestemme antall tilkoblede regioner bruker vi bwlabel til å merke hver tilkoblede region av 1 «s. Den første utgangen er etikettmatrisen (0 der inngangen var null og en hvilken som helst verdi i området 1...N der det var en 1 i inngangen der N er indeksen til den tilkoblede gruppen den tilhører). Den andre utgangen er antall regioner (antall klikk som kreves for å åpne dem). Resultatet av bwlabel vises på bildet til venstre.
Vi utvider den første utgangen av bwlabel ved hjelp av imdilate (alle ikke-nuller utvides) ved hjelp av en 3 x 3 matrise av 1 «s. Resultatet vises på bildet i midten.
For å bestemme de gjenværende klikkene teller vi deretter rutene som ikke er i dette utvidede området (~imdilate()) og ikke en gruve (-x) (hvite firkanter i bildet til høyre) og legg dette til totalt antall åpne regioner (antall forskjellige farger i bildet til venstre ) for å 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øsningen oppretter en anonym funksjon med navnet ans kan deretter sendes en 2D-matrise med 0 «s og 1» s. Logikken er den samme som MATLAB-svaret mitt, men bruker noen triks som Octave har å tilby for å spare plass.
Denne løsningen krever at image -pakken er installert .
Svar
MATL, 24 22 21 byte (ikke-konkurrerende )
1 byte lagret takket være @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Prøv det på MATL Online
Forklaring
Igjen, dette ligner på MATLAB og Octave svar på dette spørsmålet.
% 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 Dessverre ble
bwlabeln-funksjonaliteten introdusert til MATL etter utfordring ble lagt ut.