3BV Minesweeper deska představuje minimální počet levých kliknutí potřebných k vyřešení desky, pokud již znáte řešení. Je zkratkou pro “ Bechtels Benchmark Value „. Zde je jeho web to vysvětluje.
Níže je vyřešená deska Hledání min. Vlajky označují miny; dlaždice bez min označují počet sousedních dolů, včetně diagonálně, kromě toho, že dlaždice, které by měly mít “ 0 „, zůstanou prázdné. Obrázek ukazuje, na které dlaždice je třeba kliknout, aby se hrací plán vyřešil.
Kliknutí započítaná do 3BV jsou:
- Jeden pro každou zaplavenou oblast prázdných dlaždic (sousedících nulové miny) a jejich neprázdných sousedů.
- Jeden pro sebe jiné než těžební dlaždice.
Jiný příklad (3BV = 39)
Vzhledem k 2D hodnotovému poli 0 pro clear a 1 pro důl (nebo booleovský), vrátit 3BV .
Rozměry desky budou nejméně 8×8 a maximálně 2 4×30, včetně. Váš program by měl zpracovávat všechny možné desky, nejen příklady.
Poznámka: Deska nikdy nebude obsahovat pouze miny.
Příklad 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 Komentáře
- Je pole celých čísel v pořádku jako vstup? Každé celé číslo kóduje jeden řádek.
- @KarlNapf Ne. Vstup by měl být rozpoznatelný jako deska, jak je znázorněno.
- Mohli byste poskytnout více testovacích případů, případně včetně vstupu založeného na zobrazeném obrázky a možná testovací případ maximálních rozměrů?
odpověď
MATLAB, 92 90 86 83 79 74 72 bytů
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N Toto řešení přijímá vstup ve formě 2D matice 0 „sa 1“ sa zobrazí hodnotu 3BV pro zadaný vstup.
Zde je mírně upravená ukázka v Octave pro ty z vás bez MATLABu.
Vysvětlení
Vstupní matice je dilatována pomocí matice 3 x 3 1 „sa potom obrácena (pomocí ~), který identifikuje všechny body, které nemají miny jako sousedy (1) nebo do (). K určení počtu připojených oblastí používáme bwlabel k označení každé připojené oblasti 1 „. Prvním výstupem je matice štítků (0 kde byl vstup nulový a libovolná hodnota v rozsahu 1...N kde byl 1 na vstupu, kde N je index připojené skupiny, do které patří). Druhým výstupem je počet oblastí (počet kliknutí nutných k jejich otevření). Výsledek bwlabel je zobrazen na obrázku vlevo.
Rozšiřujeme první výstup bwlabel pomocí imdilate (všechny nuly jsou rozbaleny) pomocí matice 3 x 3 1 „s. Výsledek se zobrazí na obrázku uprostřed.
Abychom určili zbývající kliknutí, spočítáme čtverce, které nejsou v této rozšířené oblasti (~imdilate()) a ne důl (-x) (bílé čtverečky na obrázku vpravo) a přidejte to k celkovému počtu otevřených oblastí (počet různých barev na obrázku vlevo ) pro získání 3BV.
Odpověď
Octave, 86 84 79 66 bajtů
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Toto řešení vytvoří anonymní funkci s názvem ans, která poté lze předat 2D matici 0 „sa 1“ s. Logika je stejná jako moje odpověď MATLABu, ale používá několik triků, které Octave nabízí, aby ušetřil místo.
Toto řešení vyžaduje, aby byl nainstalován balíček image .
Odpověď
MATL, 24 22 21 bajtů (nekonkurenční )
1 bajt uložen díky @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Zkuste to na MATL Online
Vysvětlení
Opět je to podobné jako moje MATLAB a Octave odpovědi na tuto otázku.
% 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 Komentáře
- Proč nekonkurovat?
- @CalculatorFeline Funkce
bwlabelnbyla bohužel zavedena do MATL po výzva byla zveřejněna.