Il 3BV di un Campo minato rappresenta il numero minimo di clic sinistro necessari per risolvere la bacheca se conosci già la soluzione. Sta per ” Bechtel “s Board Benchmark Value “. Here” s suo site che lo spiega.
Di seguito è riportato un consiglio risolto di Campo minato. Le bandiere indicano le mine; le tessere senza mine indicano il conteggio delle mine adiacenti, anche in diagonale, tranne che le tessere che dovrebbero avere ” 0 ” vengono invece lasciate vuote. Limmagine mostra quali tessere devono essere cliccate per risolvere il tabellone.
I clic conteggiati per il 3BV sono:
- Uno per ogni area allagata di tessere vuote (zero mine adiacenti) e dei loro vicini non vuoti.
- Uno per ogni altro riquadro non minerario.
Un altro esempio (3BV = 39)
Dato un array 2D di valori, 0 per cancella e 1 per mina (o booleano), restituisci 3BV .
Le dimensioni di una lavagna saranno almeno 8 x 8 e al massimo 2 4×30, incluso. Il tuo programma dovrebbe gestire tutte le schede possibili, non solo gli esempi.
Nota: una scheda non conterrà mai solo mine.
I / O di esempio:
[[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 Commenti
- Un array di numeri interi va bene come input? Ogni numero intero codifica una riga.
- @KarlNapf No. Linput dovrebbe essere riconoscibile come una scheda come mostrato.
- Potresti fornire più casi di test, possibilmente includendo linput in base al immagini e forse un test case di dimensioni massime?
Risposta
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 Questa soluzione accetta linput sotto forma di una matrice 2D di 0 “se 1” se visualizzerà il valore 3BV per linput fornito.
Ecco una demo leggermente modificata in Octave per quelli di voi senza MATLAB.
Spiegazione
La matrice di input viene dilatata utilizzando una matrice 3 x 3 di 1 “se poi invertita (utilizzando ~) che identifica tutti i punti che non hanno miniere come vicini (1) o do (). Per determinare il numero di regioni connesse, utilizziamo bwlabel per etichettare ciascuna regione connessa di 1 “. Il primo output è la matrice delletichetta (0 dove linput era zero e qualsiasi valore nellintervallo 1...N dove cera un 1 nellinput dove N è lindice del gruppo connesso a cui appartiene). Il secondo output è il numero di regioni (il numero di clic richiesti per aprirle). Il risultato del bwlabel è mostrato nellimmagine a sinistra.
Espandiamo il primo output di bwlabel utilizzando imdilate (tutti i non zeri vengono espansi) utilizzando una matrice 3 x 3 di 1 “. Il risultato è mostrato nellimmagine al centro.
Per determinare i clic rimanenti, contiamo quindi i quadrati che non si trovano in questa regione espansa (~imdilate()) e non una miniera (-x) (quadrati bianchi nellimmagine a destra) e aggiungila al numero totale di regioni aperte (il numero di colori diversi nellimmagine a sinistra ) per ottenere 3BV.
Risposta
Ottava, 86 84 79 66 byte
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Questa soluzione crea una funzione anonima denominata ans che può quindi essere passata una matrice 2D di 0 “se 1“. La logica è la stessa della mia risposta MATLAB ma utilizza alcuni trucchi che Octave ha da offrire per risparmiare spazio.
Questa soluzione richiede che il pacchetto image sia installato .
Risposta
MATL, 24 22 21 byte (non in competizione )
1 byte salvato grazie a @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Provalo su MATL Online
Spiegazione
Ancora una volta, questo è simile alle mie risposte MATLAB e Octave a questa domanda.
% 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 Commenti
- Non competere perché?
- @CalculatorFeline Purtroppo la funzionalità
bwlabelnè stata introdotta in MATL dopo il la sfida è stata pubblicata.