De 3BV van een Mijnenveger bord geeft het minimum aantal links klikken aan dat nodig is om het bord op te lossen als je de oplossing al kent. Het staat voor ” Bechtel “s Board Benchmark Value “. Hier” s zijn site waarin het wordt uitgelegd.
Hieronder staat een opgelost Mijnenveger-bord. De vlaggen geven mijnen aan; tegels zonder mijnen geven het aantal aangrenzende mijnen aan, ook diagonaal, behalve dat tegels die ” 0 ” zouden moeten hebben, leeg worden gelaten. De afbeelding laat zien op welke tegels moet worden geklikt om het bord op te lossen.
Klikken geteld voor de 3BV zijn:
- Eén voor elk met overstromingen gevuld gebied met lege tegels (nul mijnen aangrenzend) en hun niet-lege buren.
- Eén voor elkaar niet-mijntegel.
Nog een voorbeeld (3BV = 39)
Gegeven een 2D-array met waarden, 0 voor clear en 1 voor een mijn (of een boolean), retourneren de 3BV .
De afmetingen van een bord zijn minimaal 8×8 en maximaal 2 4×30, inclusief. Je programma moet alle mogelijke borden behandelen, niet alleen de voorbeelden.
Opmerking: een bord zal nooit alleen mijnen bevatten.
Voorbeeld 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 Reacties
- Is een array van gehele getallen ok als invoer? Elk geheel getal codeert één rij.
- @KarlNapf Nee. De invoer moet herkenbaar zijn als een bord, zoals weergegeven.
- Kunt u meer testcases opgeven, mogelijk inclusief de invoer op basis van de weergegeven afbeeldingen, en misschien een testcase met maximale afmetingen?
Antwoord
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 Deze oplossing accepteert de invoer in de vorm van een 2D-matrix van 0 “s en 1” s en geeft de 3BV-waarde weer voor de opgegeven invoer.
Hier is een licht gewijzigde demo in Octave voor degenen onder u zonder MATLAB.
Uitleg
De invoermatrix wordt gedilateerd met een 3 x 3 matrix van 1 “s en vervolgens omgekeerd (met ~) die alle punten identificeert die geen mijnen hebben als buren (1) of doe (). Om het aantal verbonden regios te bepalen, gebruiken we bwlabel om elke verbonden regio van 1 “s te labelen. De eerste uitvoer is de labelmatrix (0 waarbij de invoer nul was en een willekeurige waarde in het bereik 1...N waar een 1 in de invoer waar N de index is van de verbonden groep waartoe het behoort). De tweede uitvoer is het aantal regios (het aantal klikken dat nodig is om ze te openen). Het resultaat van de bwlabel wordt weergegeven in de afbeelding aan de linkerkant.
We breiden de eerste uitvoer van bwlabel uit met imdilate (alle niet-nullen worden uitgebreid) met een 3 x 3 matrix van 1 “s. Het resultaat wordt weergegeven in de afbeelding in het midden.
Om de resterende klikken te bepalen, tellen we de vierkanten die niet in dit uitgevouwen gebied staan (~imdilate()) en niet een mijn (-x) (witte vierkantjes in de afbeelding aan de rechterkant) en voeg dit toe aan het totale aantal open gebieden (het aantal verschillende kleuren in de afbeelding aan de linkerkant ) om de 3BV te krijgen.
Answer
Octave, 86 84 79 66 bytes
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Deze oplossing creëert een anonieme functie met de naam ans die kan dan een 2D-matrix van 0 “s en 1” s worden doorgegeven. De logica is hetzelfde als mijn MATLAB-antwoord, maar gebruikt een paar trucs die Octave te bieden heeft om ruimte te besparen.
Deze oplossing vereist dat het image -pakket is geïnstalleerd .
Antwoord
MATL, 24 22 21 bytes (niet-concurrerend )
1 byte opgeslagen dankzij @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Probeer het op MATL Online
Uitleg
Nogmaals, dit is vergelijkbaar met mijn MATLAB- en Octave-antwoorden op deze vraag.
% 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 Reacties
- Niet-concurrerend waarom?
- @CalculatorFeline Helaas is de
bwlabeln-functionaliteit geïntroduceerd in MATL na de uitdaging geplaatst.