Considere las matrices diagonales de bloques binarios que tienen bloques cuadrados de 1s en la diagonal principal, y son 0 en todas partes. Llamemos a esas matrices matrices "válidas".

Por ejemplo, aquí hay algunas matrices 4x4 válidas:

1 0 0 0     1 1 0 0     1 0 0 0     1 0 0 0     1 1 0 0    1 1 1 1
0 1 0 0     1 1 0 0     0 1 1 0     0 1 1 1     1 1 0 0    1 1 1 1
0 0 1 0     0 0 1 0     0 1 1 0     0 1 1 1     0 0 1 1    1 1 1 1
0 0 0 1     0 0 0 1     0 0 0 1     0 1 1 1     0 0 1 1    1 1 1 1

Tenga en cuenta que una forma alternativa de describir tales matrices es que hay una cadena de bloques cuadrados 1 desde la parte superior izquierda a la inferior derecha, tocando de esquina a esquina, y en todas partes es 0.

Por el contrario, aquí hay algunas matrices 4x4 no válidas:

1 0 1 0     1 0 1 0     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 1 1 1     0 1 0 1     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
1 0 0 1     1 0 1 0     0 0 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 0 1 0     0 1 0 1     0 0 0 1     1 0 0 0     0 0 1 1    0 0 0 0

Se le dará una npor nmatriz binaria como entrada - ¿cuál es el número mínimo de 0bits de que tendrá que establecer a1 fin de obtener una matriz válida?

Puede escribir una función o programa tomando cualquier formato conveniente de cadena, lista o matriz que represente un nbyn matriz de 0s y 1s (siempre que no esté preprocesada). Las filas deben estar claramente separadas de alguna manera, por lo que no se permiten formatos como una matriz de bits 1D.

Este es el código de golf , por lo que el objetivo es minimizar el número de bytes en su programa.

Ejemplos

Por ejemplo, si la entrada es

0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1

entonces la respuesta es 5, ya que puede configurar cinco 0bits 1para obtener:

1 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 1 0
0 0 0 0 1

y este es el número mínimo requerido. Sin embargo, si la entrada fue

0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

entonces la respuesta es 24, ya que la única matriz de 5x5 válida donde está la esquina superior derecha 1es la matriz de todos1 s.

Casos de prueba

Las pruebas se representan aquí como una matriz 2D de enteros.

[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

Notas

• Desafío relacionado: imprimir una matriz de bloques en diagonal
• Inspiración: Freedom Factory, Google Code Jam 2016 Problema 2D

MATL , 46 43 bytes

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

La entrada es una matriz 2D con punto y coma como separador de filas. Por ejemplo, la entrada para el último caso de prueba es

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Pruébalo en línea! O verifique todos los casos de prueba (código ligeramente modificado para tomar todas las entradas; los resultados aparecen después de unos segundos)

Explicación

Deje que la entrada sea una matriz N × N. El código primero calcula todas las tuplas ( N +1) de tamaños de bloque que producen el tamaño de matriz apropiado. Por ejemplo, para N = 4 los tuplas son 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. Para cada tupla construye la matriz diagonal de bloque con esos tamaños de bloque. Luego verifica si la matriz cubre todas las 1entradas en la entrada, y si es así toma nota de la cantidad de 1entradas que no estaban presentes en la entrada. El resultado final es el mínimo de todos los números obtenidos.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each 
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display

Python con numpy, 102

from numpy import*
lambda M:sum(diff([k for k in range(len(M)+1)if(M|M.T)[:k,k:].any()-1])**2)-M.sum()

Un algoritmo eficiente. Encuentra los "puntos de cuello" en la diagonal que pueden separar bloques. Estos tienen todos los 0 arriba y derecha, así como abajo y a la izquierda. Los bloques mínimos son aquellos entre los puntos del cuello.

??000
??000
00???
00???
00???

La longitud de un bloque es la diferencia entre puntos de cuello consecutivos, por lo que su área total de la suma de cuadrados de estos. Restando la suma de la matriz original, se obtiene el número de vueltas necesarias de 0 a 1.

Pyth, 45 bytes

[email protected]^+LsYN2d+0._ds.pM./lQss

Tarea difícil, por lo que es bastante larga.

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación:

s.pM./lQcalcula todas las particiones enteras de len(matrix). ms.b^+LsYN2d+0._dlos convierte en pares de coordenadas. Por ejemplo, la partición [1, 2, 2]de 5se convierte en [[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4].

[email protected]luego filtra las particiones, que se superponen por completo a la matriz ( .DRlQx1sQcalcula todos los pares de coordenadas de las celdas activas en la matriz).

-hSlM...ss cuenta las celdas de cada partición restante, elige la que tenga menos celdas y resta las celdas ya activas.

Matrices , 180 bytes (sin competencia)

Matricks es un nuevo esolang que creé recientemente para tratar problemas de matriz (como este), al tener solo 2 tipos de datos: flotantes y matrices. Todavía no está completamente presentado, y todavía le faltan muchas operaciones (tuve que agregar algunas funcionalidades para este desafío). De todos modos, aquí está el código:

il=1:j3;:bdx;;;s1::L;j1;;
b{q:1;mgr:c;|gc:r;|(r=c)|(gr-1:c;|gr:c+1;)&(rec)|(gr+1:c;|gr:c-1;)&(cer):l:L;};z:(l-1)/2;B1;s1::g1:;-1;ig1:;=0:j2;:j1;;
s1::d{q:1;};;kg1:;-g:;;
kg:;*-1+1;

Explicación

La primera parte, il=1:j3;:...;verifica si la matriz es de tamaño 1. Si es así, salta a la última línea kg:;*-1+1;, que es una 0 <-> 1función simple .

De lo contrario, continúa con el resto del código. bdx;;;establece la celda 0,0en la suma actual y s1::L;j1;crea un contador en la celda en la fila de abajo.

La siguiente línea es un poco más complicada. Es un ciclo que corre ntiempos, nsiendo el tamaño de la matriz. Usaré el tercer caso de prueba como ejemplo. Cuando llegamos a la segunda línea, la matriz se ve así:

1 0 1
2 0 0

Primero, entramos en la comprensión matricial {q:1;m...;}. Esto hace la diagonal, y hace todo lo posible para limpiar 0 que necesitan ser rellenados. Todo esto se logra utilizando operadores booleanos simples. Luego, lo anteponemos a la matriz actual, dando esto:

    V--data we want to keep
1 1 1 0 1 <-|
1 1 2 0 0 <-- old matrix

Luego, cortamos la matriz anterior usando z:(l-1)/2;y rotamos toda la matriz hacia la izquierda usando B1;. Eso nos da una matriz lista para la próxima iteración, que se ve así:

1 1 1
2 1 1

Finalmente, disminuimos el contador, lo verificamos y continuamos con ig1:;=0:j2;:j1;;

Una vez que se rompe el bucle, encontramos la nueva suma y establecemos el lugar anterior del contador con s1::d{q:1;};;. Finalmente, tomamos la diferencia y regresamos kg1:;-g:;;. kestablece la matriz actual en un valor y la impresión es implícita.

...

Como puede ver, Matricks es bastante detallado, y no es un muy buen lenguaje de golf. Pero diablos, quería mostrarlo.