Calcule el 3BV de un tablero de Buscaminas

17

El 3BV de un tablero de Buscaminas representa el número mínimo de clics izquierdos necesarios para resolver el tablero si ya conoce la solución. Es sinónimo de "Valor de referencia de la Junta de Bechtel". Aquí está su sitio explicándolo.

A continuación se muestra un tablero de Buscaminas resuelto. Las banderas indican minas; las fichas sin minas indican el recuento de minas adyacentes, incluso en diagonal, excepto que las fichas que deberían tener "0" se dejan en blanco. La imagen muestra en qué mosaicos se debe hacer clic para resolver el tablero.

Contando 3BV

Los clics contados hacia el 3BV son:

  • Uno para cada área llena de inundaciones de mosaicos en blanco (cero minas adyacentes) y sus vecinos no en blanco.
  • Uno para el otro azulejo no minero.

Otro ejemplo (3BV = 39)

Tablero de buscaminas resuelto Clics requeridos


Dada una matriz de valores 2D, 0para clear y 1para una mina (o un booleano), devuelve el 3BV .

Las dimensiones de una placa serán de al menos 8x8, y como máximo 24x30, inclusive. Su programa debe manejar todos los tableros posibles, no solo los ejemplos.

Nota: Un tablero nunca contendrá solo minas.

Ejemplo de E / 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
mbomb007
fuente
¿Una matriz de enteros está bien como entrada? Cada número entero codifica una fila.
Karl Napf
@KarlNapf No. La entrada debe ser reconocible como una placa como se muestra.
mbomb007
¿Podría proporcionar más casos de prueba, posiblemente incluyendo la entrada basada en las imágenes mostradas, y tal vez un caso de prueba de dimensiones máximas?
millas

Respuestas:

15

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

Esta solución acepta la entrada en forma de una matriz 2D de 0 y 1 y mostrará el valor de 3BV para la entrada proporcionada.

Aquí hay una demostración ligeramente modificada en Octave para aquellos de ustedes sin MATLAB.

Explicación

La matriz de entrada se dilata usando una matriz de 3 x 3 1y luego se invierte (usando ~) que identifica todos los puntos que no tienen minas como vecinos ( 1) o do ( 0). Para determinar el número de regiones conectadas, usamos bwlabelpara etiquetar cada región conectada de 1's. La primera salida es la matriz de etiquetas ( 0donde la entrada era cero y cualquier valor en el rango 1...Ndonde había un 1en la entrada donde Nestá el índice del grupo conectado al que pertenece). El segundo resultado es la cantidad de regiones (la cantidad de clics necesarios para abrirlas). El resultado del bwlabelse muestra en la imagen de la izquierda.

ingrese la descripción de la imagen aquí

Expandimos la primera salida de bwlabelusar imdilate(todos los no ceros se expanden) usando una matriz de 3 x 3 de 1's. El resultado se muestra en la imagen en el medio.

Para determinar los clics restantes, contamos los cuadrados que no están en esta región expandida ( ~imdilate()) y no una mina ( -x) (cuadrados blancos en la imagen de la derecha) y agregamos esto al número total de regiones abiertas (el número de diferentes colores en la imagen de la izquierda) para obtener el 3BV.

Suever
fuente
9

Octava, 86 84 79 66 bytes

@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:))

Esta solución crea una función anónima llamada ansque luego se puede pasar una matriz 2D de 0'sy 1' s. La lógica es la misma que mi respuesta de MATLAB, pero utiliza algunos trucos que Octave tiene para ofrecer para ahorrar espacio.

Esta solución requiere que el imagepaquete esté instalado.

Demo aquí

Suever
fuente
2

MATL, 24 22 21 bytes (no competidor)

1 byte guardado gracias a @Luis

4Y6Z+~l2#ZIw7MZ+G+~z+

Pruébalo en MATL Online

Explicación

Nuevamente, esto es similar a mis respuestas de MATLAB y Octave a esta pregunta.

        % 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 
Suever
fuente
¿No compitiendo por qué?
CalculatorFeline
1
@CalculatorFeline Desafortunadamente, la bwlabelnfuncionalidad se introdujo en MATL después de que se publicó el desafío.
Suever