Le 3BV dun Démineur représente le nombre minimum de clics gauche requis pour résoudre le tableau si vous connaissez déjà la solution. Il représente la » Bechtel « s Board Benchmark Value « . Ici » s son site expliquant.
Ci-dessous, un tableau de démineur résolu. Les drapeaux indiquent les mines; les tuiles sans mines indiquent le nombre de mines adjacentes, y compris en diagonale, sauf que les tuiles qui devraient avoir » 0 » sont laissées vides à la place. Limage montre les tuiles sur lesquelles il faut cliquer pour résoudre le tableau.
Les clics comptabilisés pour le 3BV sont:
- Un pour chaque zone inondée de tuiles vierges (aucune mine adjacente) et de leurs voisins non vides.
- Un pour chaque autre tuile non minière.
Un autre exemple (3BV = 39)
Étant donné un tableau 2D de valeurs, 0 pour effacer et 1 pour une mine (ou un booléen), renvoie le 3BV .
Les dimensions dune planche seront dau moins 8 x 8 et dau plus 2 4×30, inclus. Votre programme doit gérer tous les tableaux possibles, pas seulement les exemples.
Remarque: Un tableau ne contiendra jamais que des mines.
Exemple dE / S:
[[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 Commentaires
- Un tableau dentiers est-il acceptable en entrée? Chaque entier code une ligne.
- @KarlNapf Non. Lentrée doit être reconnaissable comme un tableau, comme indiqué.
- Pourriez-vous fournir plus de cas de test, y compris éventuellement lentrée basée sur images et peut-être un cas de test de dimensions maximales?
Réponse
MATLAB, 92 90 86 83 79 74 72 octets
x=input("");I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N Cette solution accepte lentrée sous la forme dune matrice 2D de 0 « s et 1 » s et affichera la valeur 3BV pour lentrée fournie.
Voici une démo légèrement modifiée dans Octave pour ceux dentre vous sans MATLAB.
Explication
La matrice dentrée est dilatée en utilisant une matrice 3 x 3 de 1 « s puis inversée (en utilisant ~) qui identifie tous les points qui nont pas de mines comme voisins (1) ou do (). Pour déterminer le nombre de régions connectées, nous utilisons bwlabel pour étiqueter chaque région connectée de 1 « s. La première sortie est la matrice détiquettes (0 où lentrée était zéro et toute valeur de la plage 1...N où il y avait un 1 dans lentrée où N est lindex du groupe connecté auquel il appartient). La deuxième sortie est le nombre de régions (le nombre de clics nécessaires pour les ouvrir). Le résultat du bwlabel est affiché dans limage de gauche.
Nous développons la première sortie de bwlabel en utilisant imdilate (tous les non-zéros sont développés) en utilisant une matrice 3 x 3 de 1 « s. Le résultat est affiché dans limage au milieu.
Pour déterminer les clics restants, nous comptons ensuite les carrés qui ne sont pas dans cette région développée (~imdilate()) et non une mienne (-x) (carrés blancs dans limage de droite) et ajoutez ceci au nombre total de régions ouvertes (le nombre de couleurs différentes dans limage de gauche) ) pour obtenir le 3BV.
Réponse
Octave, 86 84 79 66 octets
@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:)) Cette solution crée une fonction anonyme nommée ans qui peut alors être passée une matrice 2D de 0 « s et 1 » s. La logique est la même que ma réponse MATLAB mais utilise quelques astuces quOctave a à offrir pour économiser de lespace.
Cette solution nécessite que le package image soit installé .
Réponse
MATL, 24 22 21 octets (non concurrents )
1 octet sauvé grâce à @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Essayez-le à MATL en ligne
Explication
Encore une fois, ceci est similaire à mes réponses MATLAB et Octave à cette question.
% 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 Commentaires
- Pourquoi ne pas concurrencer?
- @CalculatorFeline Malheureusement, la fonctionnalité
bwlabelna été introduite dans MATL après le défi a été publié.