3BV a unui Minesweeper reprezintă numărul minim de clicuri stânga necesare pentru a rezolva placa dacă știți deja soluția. Reprezintă " Benchel „Board Benchmark Value ". Aici” s lui site explicându-l.
Mai jos este o placă Minesweeper rezolvată. Steagurile indică minele; plăcile fără mine indică numărul de mine adiacente, inclusiv în diagonală, cu excepția faptului că plăcile care ar trebui să aibă " 0 " sunt lăsate necompletate. Imaginea arată ce plăci trebuie făcute clic pentru a rezolva placa.
Clicurile numărate pentru 3BV sunt:
- Unul pentru fiecare zonă plină de inundații de plăci goale (zero minere adiacente) și vecinii lor ne-gol.
- Una pentru cealaltă țiglă care nu este mină.
Un alt exemplu (3BV = 39)
Având în vedere o matrice 2D de valori, 0 pentru clear și 1 pentru o mină (sau un boolean), returnează 3BV .
Dimensiunile unei plăci vor fi de cel puțin 8×8 și cel mult 2 4×30, inclusiv. Programul dvs. ar trebui să gestioneze toate plăcile posibile, nu doar exemplele.
Notă: o placă nu va conține niciodată numai mine.
Exemplu 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 Comentarii
- Este o serie de numere întregi în regulă ca intrare? Fiecare număr întreg codifică un rând.
- @KarlNapf nu. imagini și poate un caz de testare a dimensiunilor maxime?
Răspuns
MATLAB, 92 90 86 83 79 74 72 octeți
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N Această soluție acceptă intrarea sub forma unei matrice 2D de 0 „s și 1” s și va afișa valoarea 3BV pentru intrarea furnizată.
Aici este o ușoară modificare demo în Octave pentru cei dintre voi fără MATLAB.
Explicație
Matricea de intrare este dilatată folosind o matrice de 3 x 3 de 1 „s și apoi inversată (folosind ~) care identifică toate punctele care nu au mine ca vecini (1) sau pe care le face (). Pentru a determina numărul de regiuni conectate, folosim bwlabel pentru a eticheta fiecare regiune conectată a 1 „s. Prima ieșire este matricea etichetei (0 unde intrarea a fost zero și orice valoare din intervalul 1...N unde a existat un 1 în intrare unde N este indicele grupului conectat de care aparține). A doua ieșire este numărul de regiuni (numărul de clicuri necesare pentru a le deschide). Rezultatul bwlabel este afișat în imaginea din stânga.
Extindem prima ieșire a bwlabel folosind imdilate (toate non-zerourile sunt extinse) folosind o matrice 3 x 3 de 1 „s. Rezultatul este afișat în imaginea din mijloc.
Pentru a determina clicurile rămase, contorizăm pătratele care nu se află în această regiune extinsă (~imdilate()) și nu a mea (-x) (pătrate albe în imaginea din dreapta) și adăugați acest lucru la numărul total de regiuni deschise (numărul de culori diferite din imaginea din stânga ) pentru a obține 3BV.
Răspuns
Octave, 86 84 79 66 octeți
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Această soluție creează o funcție anonimă numită ans se poate trece apoi o matrice 2D de 0 „s și 1” s. Logica este aceeași cu răspunsul meu MATLAB, dar folosește câteva trucuri pe care Octave le poate oferi pentru a economisi spațiu.
Această soluție necesită instalarea pachetului image .
Răspuns
MATL, 24 22 21 octeți (neconcurenți )
1 octet salvat datorită @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Încercați-l la MATL Online
Explicație
Din nou, acest lucru este similar cu răspunsurile mele MATLAB și Octave la această întrebare.
% 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 Comentarii
- De ce nu se concurează?
- @CalculatorFeline Din păcate, funcționalitatea
bwlabelna fost introdusă în MATL după provocare a fost postată.