Рассмотрим двоичные блочные диагональные матрицы, которые имеют квадратные блоки 1 на главной диагонали и равны 0 везде. Будем называть такие матрицы «действительными» матрицами.

Например, вот некоторые допустимые матрицы 4x4:

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

Обратите внимание, что альтернативный способ описания таких матриц состоит в том, что существует цепочка из блоков квадрата 1 от верхнего левого угла до нижнего правого, касаясь угла к углу, и везде остальное равно 0.

Для контраста, вот некоторые недопустимые матрицы 4x4:

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

Вам будет дано nпо nбинарной матрице в качестве входных данных - какое минимальное количество 0битов вам нужно задать 1, чтобы получить действительную матрицу?

Вы можете написать функцию или программу взятие в любом удобной строке, список или матрице формате , представляющее собой nпо nматрице 0 и 1 ( до тех пор , как он не препроцессор). Строки должны быть четко разделены, поэтому форматы, такие как одномерный массив битов, не допускаются.

Это код-гольф , поэтому цель состоит в том, чтобы минимизировать количество байтов в вашей программе.

Примеры

Например, если вход

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битов, 1чтобы получить:

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

и это минимальное количество требуется. Однако, если вход был

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, поскольку единственная действительная матрица 5x5, где справа вверху - 1это матрица всех 1s.

Контрольные примеры

Тесты представлены здесь как двумерный массив целых чисел.

[[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

Ноты

• Задача, связанная с данной: Распечатать блочно-диагональную матрицу
• Вдохновение: Freedom Factory, Google Code Jam 2016, задача 2D

MATL , 46 43 байта

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

Ввод - это двумерный массив с точкой с запятой в качестве разделителя строк. Например, вход для последнего контрольного примера

[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]

Попробуйте онлайн! Или проверьте все контрольные примеры (код немного изменен, чтобы принять все входные данные; результаты появляются через несколько секунд)

объяснение

Пусть вход будет матрицей N × N. Сначала код вычисляет все ( N + 1) кортежи с размерами блоков, которые дают соответствующий размер матрицы. Например, для N = 4 кортежи являются 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. Для каждого кортежа он строит блок-диагональную матрицу с этими размерами блоков. Затем он проверяет, покрывает ли матрица все 1записи на входе, и, если это так, принимает к сведению количество 1записей, которых не было на входе. Окончательный результат - минимум всех полученных чисел.

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

Питон с 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()

Эффективный алгоритм. Находит «точки шеи» на диагонали, которые могут разделять блоки. Они имеют все 0 сверху и справа, а также снизу и слева. Минимальные блоки - те, которые находятся между точками шеи.

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

Длина блока - это разница между последовательными точками шеи, поэтому их общая площадь равна сумме квадратов. Вычитая сумму из исходной матрицы, мы получим необходимое количество бросков от 0 до 1.

Pyth, 45 байт

-hSlMf@I.DRlQx1sQTms.b^+LsYN2d+0._ds.pM./lQss

Задача сложная, поэтому довольно длинная.

Попробуйте онлайн: демонстрация или тестовый набор

Объяснение:

s.pM./lQвычисляет все целые разделы len(matrix). ms.b^+LsYN2d+0._dпреобразует их в пары координат. Например раздел [1, 2, 2]из 5преобразуется в [[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4].

f@I.DRlQx1sQTзатем фильтры для разделов, которые полностью перекрывают матрицу ( .DRlQx1sQвычисляет все пары координат активных ячеек в матрице).

-hSlM...ss подсчитывает ячейки каждого из оставшихся разделов, выбирает ячейку с наименьшим количеством ячеек и вычитает уже активные ячейки.

Матрицы , 180 байт (неконкурентные)

Matricks - это новый esolang, который я создал совсем недавно для решения проблем с матрицами (таких как этот), имея только 2 типа данных: числа с плавающей запятой и матрицы. Он еще не полностью реализован, и все еще содержит много пропущенных операций (мне пришлось добавить некоторые функции для этой задачи). Во всяком случае, вот код:

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;

объяснение

Первая часть il=1:j3;:...;проверяет, имеет ли массив размер 1. Если это так, он переходит на последнюю строку kg:;*-1+1;, которая является простой 0 <-> 1функцией.

Иначе, это продолжается с остальной частью кода. bdx;;;устанавливает ячейку 0,0в текущую сумму и s1::L;j1;создает счетчик в ячейке в строке ниже.

Следующая строка немного сложнее. Это цикл, который работает nраз, nбудучи размером матрицы. Я буду использовать третий тестовый пример в качестве примера. Когда мы впервые попадаем на вторую строку, матрица выглядит так:

1 0 1
2 0 0

Сначала мы углубимся в понимание матрицы {q:1;m...;}. Это делает диагональ и старается очистить 0, которые нужно заполнить. Все это выполняется с помощью простых логических операторов. Затем мы добавляем его к текущей матрице, давая это:

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

Затем мы обрезаем старую матрицу, используя z:(l-1)/2;, и поворачиваем всю матрицу влево, используя B1;. Это дает нам матрицу, готовую к следующей итерации, которая выглядит следующим образом:

1 1 1
2 1 1

Наконец, мы уменьшаем счетчик, проверяем его и продолжаем ig1:;=0:j2;:j1;;

Как только цикл разорван, мы находим новую сумму и устанавливаем старую точку счетчика с помощью s1::d{q:1;};;. Наконец, мы берем разницу и возвращаемся kg1:;-g:;;. kустанавливает текущий массив в значение, и печать неявная.

...

Как видите, Matricks довольно многословен и не очень хорош для игры в гольф. Но, черт возьми, я хотел показать это.