iv id = ” 3BV 368d502a8c ”>
Minesweeper -taulu edustaa vähimmäismäärää vasemmalle napsautuksia, joita tarvitaan taulun ratkaisemiseksi, jos tiedät jo ratkaisun. Se tarkoittaa ” Bechtelin taulun vertailuarvoa ”. Tässä ”s hänen sivusto selittää sen.
Alla on ratkaistu Minesweeper-lauta. Liput osoittavat miinoja; laatat ilman kaivoksia osoittavat vierekkäisten miinojen määrän, mukaan lukien vinosti, paitsi että laatat, joiden tulisi olla ” 0 ”, jätetään tyhjiksi. Kuvassa näkyy, mitä ruutuja on napsautettava taulun ratkaisemiseksi.
3BV: hen lasketut napsautukset ovat:
- Yksi kutakin tulvien täyttämää aluetta kohti tyhjiä ruutuja (nolla miinaa vierekkäin) ja niiden muita naapureita.
- Yksi toisilleen ei-minun ruutu.
Toinen esimerkki (3BV = 39)
Annettu 2D-arvoryhmä, 0 selkeälle ja 1 kaivokselle (tai booleanille), palauta 3BV .
Taulun mitat ovat vähintään 8×8 ja enintään 2 4×30, mukaan lukien. Ohjelmasi tulisi käsitellä kaikkia mahdollisia levyjä, ei vain esimerkkejä.
Huomaa: Taulu ei koskaan sisällä vain kaivoksia.
Esimerkki 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 kommentit
- Onko joukko kokonaislukuja kunnossa syötteenä? Jokainen kokonaisluku koodaa yhden rivin.
- @KarlNapf Ei. Syötteen tulisi olla tunnistettavissa tauluna kuvan osoittamalla tavalla.
- Voisitko antaa lisää testitapauksia, mahdollisesti sisältäen syötteen näytetyn näytön perusteella kuvia, ja kenties enimmäismitatapa?
Vastaa
MATLAB, 92 90 86 83 79 74 72 tavua
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N Tämä ratkaisu hyväksyy syötteen 0 ”s ja 1” s: n 2D-matriisina ja näyttää toimitetun tulon 3BV-arvon.
Tässä on hieman muokattu esittely Octavessa niille teistä, joilla ei ole MATLABia.
Selitys
Syöttömatriisi laajennetaan 3 x 3 -matriisilla, jossa on 1 ”ja sitten käännetään (käyttämällä ~), joka tunnistaa kaikki pisteet, joilla ei ole kaivoksia naapureina (1) tai jotka tekevät (). Yhdistettyjen alueiden lukumäärän määrittämiseksi käytämme bwlabel -merkintää jokaisen 1 ”: n yhdistetyn alueen merkitsemiseen. Ensimmäinen lähtö on tarramatriisi (0 jossa tulo oli nolla ja mikä tahansa arvo alueella 1...N, jossa oli 1 syötteessä, jossa N on yhdistetyn ryhmän hakemisto, johon se kuuluu). Toinen lähtö on alueiden lukumäärä (niiden avaamiseen tarvittavien napsautusten määrä). bwlabel -tulos näkyy vasemmalla olevassa kuvassa.
Laajennamme bwlabel -kuvion ensimmäistä tulosta imdilate (kaikki ei-nollat laajennetaan) käyttämällä 3 x 3 -matriisia 1 ”s. Tulos näkyy keskellä olevassa kuvassa.
Jäljellä olevien napsautusten määrittämiseksi lasketaan sitten neliöt, jotka eivät ole tällä laajennetulla alueella (~imdilate()) eikä miinaa (-x) (valkoiset neliöt oikealla olevassa kuvassa) ja lisää tämä avoimien alueiden kokonaismäärään (vasemmalla olevan kuvan eri värien lukumäärä) ) saadaksesi 3BV: n.
Vastaa
oktaavi, 86 84 79 66 tavua
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Tämä ratkaisu luo nimettömän funktion nimeltä ans, joka voidaan sitten siirtää 2D-matriisi, jossa on 0 ”s ja 1” s. Logiikka on sama kuin MATLAB-vastaukseni, mutta käyttää muutamia temppuja, joita Octave tarjoaa tarjoamaan tilaa säästääkseen.
Tämä ratkaisu edellyttää, että image -paketti on asennettu .
vastaus
MATL, 24 22 21 tavua (ei kilpaileva) )
1 tavu tallennettu @Luis : n ansiosta
4Y6Z+~l2#ZIw7MZ+G+~z+ Kokeile osoitteessa MATL Online
Selitys
Tämä on jälleen samanlainen kuin MATLAB- ja Octave-vastaukseni tähän kysymykseen.
% 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 Kommentit
- Kilpailematon miksi?
- @CalculatorFeline Valitettavasti
bwlabeln-toiminto otettiin käyttöön MATL: n jälkeen haaste lähetettiin.