El 3BV de un Buscaminas representa el número mínimo de clics izquierdo necesarios para resolver el tablero si ya conoce la solución. Significa » Valor comparativo de la junta directiva de Bechtel «. Aquí «s su sitio explicándolo.
A continuación se muestra un tablero de Buscaminas resuelto. Las banderas indican minas; los mosaicos sin minas indican el recuento de minas adyacentes, incluso en diagonal, excepto que los mosaicos que deben tener » 0 » se dejan en blanco. La imagen muestra en qué mosaicos se debe hacer clic para resolver el tablero.
Los clics contados para el 3BV son:
- Uno por cada área inundada de mosaicos en blanco (sin minas adyacentes) y sus vecinos que no están en blanco.
- Uno para cada mosaico que no es mío.
Otro ejemplo (3BV = 39)
Dada una matriz 2D de valores, 0 para borrar y 1 para una mina (o un booleano), devuelve el 3BV .
Las dimensiones de una placa serán al menos 8×8 y como máximo 2 4×30, incluido. 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 Comentarios
- ¿Está bien una matriz de enteros como entrada? Cada número entero codifica una fila.
- @KarlNapf No. La entrada debe ser reconocible como un tablero como se muestra.
- ¿Podría proporcionar más casos de prueba, posiblemente incluyendo la entrada basada en el imágenes, y tal vez un caso de prueba de dimensiones máximas?
Respuesta
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 «sy 1» sy mostrará el valor 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 de 1 «sy luego se invierte (usando ~) que identifica todos los puntos que no tienen minas como vecinos (1) o no (). Para determinar la cantidad de regiones conectadas, usamos bwlabel para etiquetar cada región conectada de 1 «s. La primera salida es la matriz de etiquetas (0 donde la entrada era cero y cualquier valor en el rango 1...N donde había un 1 en la entrada donde N es el índice del grupo conectado al que pertenece). La segunda salida es el número de regiones (el número de clics necesarios para abrirlas). El resultado del bwlabel se muestra en la imagen de la izquierda.
Expandimos la primera salida de bwlabel usando imdilate (todos los que no son ceros se expanden) usando una matriz de 3 x 3 de 1 «s. El resultado se muestra en la imagen del 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 sume esto al número total de regiones abiertas (el número de colores diferentes en la imagen de la izquierda ) para obtener el 3BV.
Respuesta
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 ans que luego se puede pasar una matriz 2D de 0 «sy 1» s. La lógica es la misma que mi respuesta de MATLAB, pero usa algunos trucos que Octave tiene para ofrecer para ahorrar espacio.
Esta solución requiere que el paquete image esté instalado .
Respuesta
MATL, 24 22 21 bytes (no competitivo )
1 byte guardado gracias a @Luis
4Y6Z+~l2#ZIw7MZ+G+~z+ Pruébelo 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 Comentarios
- ¿Por qué no competir?
- @CalculatorFeline Lamentablemente, la funcionalidad
bwlabelnse introdujo en MATL después de se publicó el desafío.