Динамическое программирование - Самый большой квадратный блок

Вот набросок решения:

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

Начните итерацию с нижней правой ячейки и перейдите в нижний левый угол, затем перейдите на одну строку вверх и повторите.

При каждом сканировании сделайте следующее:

1. Если ячейка имеет 0 присвоить count = 0
2. Если ячейка имеет 1 и является краевой ячейкой (только нижний или правый край), присвойте count = 1
3. Для всех остальных ячеек проверьте количество ячейку справа, снизу и справа. Возьмите минимальное из них, прибавьте 1 и назначьте это количество. Сохраните глобальную переменную max_count , чтобы отслеживать максимальное количество на данный момент.

В конце обхода матрицы max_count будет иметь желаемое значение.

Сложность не больше, чем стоимость обхода матрицы.

Вот так матрица будет выглядеть после обхода. Значения в скобках - это количество, т. Е. Самый большой квадрат, который можно сделать, используя ячейку в верхнем левом углу.

1(1) 0(0) 1(1) 0(0) 1(1) 0(0)
1(1) 0(0) 1(4) 1(3) 1(2) 1(1)
0(0) 1(1) 1(3) 1(3) 1(2) 1(1)
0(0) 0(0) 1(2) 1(2) 1(2) 1(1)
1(1) 1(1) 1(1) 1(1) 1(1) 1(1)

Реализация в Python

def max_size(mat, ZERO=0):
    """Find the largest square of ZERO's in the matrix `mat`."""
    nrows, ncols = len(mat), (len(mat[0]) if mat else 0)
    if not (nrows and ncols): return 0 # empty matrix or rows
    counts = [[0]*ncols for _ in xrange(nrows)]
    for i in reversed(xrange(nrows)):     # for each row
        assert len(mat[i]) == ncols # matrix must be rectangular
        for j in reversed(xrange(ncols)): # for each element in the row
            if mat[i][j] != ZERO:
                counts[i][j] = (1 + min(
                    counts[i][j+1],  # east
                    counts[i+1][j],  # south
                    counts[i+1][j+1] # south-east
                    )) if i < (nrows - 1) and j < (ncols - 1) else 1 # edges
    return max(c for rows in counts for c in rows)

LSBRA (X, Y) означает «Самый большой квадрат с нижним правым краем в X, Y»

Псевдокод:

LSBRA(X,Y):
   if (x,y) == 0:
       0
   else:
       1+MIN( LSBRA(X-1,Y), LSBRA(X,Y-1), LSBRA(X-1,Y-1) )

(Для краевых ячеек вы можете пропустить часть MIN и просто вернуть 1, если (x, y) не равно 0.)

Работа по диагонали через сетку «волнами», например:

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 2 3 4 5 6
2 | 3 4 5 6 7
3 | 4 5 6 7 8

или, альтернативно, работайте слева направо, сверху вниз, пока вы заполняете крайние ячейки.

    0 1 2 3 4
  +----------
0 | 1 2 3 4 5
1 | 6 7 8 9 .
2 | . . . . .
3 | . . . . .

Таким образом вы будете никогда не выполняйте вычисления, в которых вы ранее не вычисляли необходимые данные - поэтому все LSBRA () «вызывают» на самом деле это просто поиск в таблице результатов ваших предыдущих вычислений (отсюда и аспект динамического программирования).

Почему это работает

Для того, чтобы иметь квадрат с правой нижней точкой в ​​X, Y - он должен содержать перекрывающиеся квадраты на один размер меньше, которые касаются каждого из трех других углов. Другими словами, чтобы иметь

XXXX
XXXX
XXXX
XXXX

, вы также должны иметь ...

XXX.    .XXX    ....    ....
XXX.    .XXX    XXX.    ....
XXX.    .XXX    XXX.    ....
....    ....    XXX.    ...X

Пока у вас есть эти 3 (каждый из LSBRA проверяет) квадратов размера N плюс текущий квадрат также «занят», у вас будет квадрат размером (N + 1).

Первый алгоритм, который приходит мне в голову, такой:

1. '&&' столбец / строка 1 со столбцом / строкой 2, если, это означает выполнение операции '&&' между каждой записью и соответствующая запись в другом столбце / строке.
2. Проверьте результирующий столбец, есть ли какая-либо длина 2 1, что означает, что мы попали в квадрат 2x2.
3. И следующий столбец с результатом первых двух. Если есть любая длина 3 1, мы попали в квадрат 3x3.
4. Повторяйте, пока не будут использованы все столбцы.
5. Повторите 1–4, начиная со столбца 2.

Я не буду показывать вам реализацию, поскольку она довольно проста, а ваша проблема звучит как домашнее задание. Вдобавок, вероятно, есть гораздо более эффективные способы сделать это, так как это станет медленным, если ввод будет очень большим.

Пусть входная матрица M : но вам не нужно хранить всю матрицу T , а только текущую и предыдущие строки.

Следующие примечания могут помочь понять общую идею:

• все квадраты с прямым нижним углом ( i-1, j), (i, j-1), (i-1, j-1) с размером s находятся внутри квадрата с прямым нижним углом (i, j) с размером s + 1.
• if есть квадрат размера s + 1 с правым нижним углом в точке (i, j), тогда размер максимального квадрата с правыми нижними углами (i-1, j), (i, j-1), (i-1, j) -1) не меньше s.
• Верно и обратное. Если размер хотя бы одного квадрата с нижними прямыми углами в (i-1, j), (i, j-1), (i-1, j-1) меньше s, то размер квадрата с правым нижним углом at (i, j) не может быть больше s + 1.

Хорошо, самый неэффективный, но простой способ:

1. выбрать первый элемент. проверьте, равно ли 1, если да, то у вас есть квадрат 1x1.

2. проверьте один ниже и один справа, если 1, затем проверьте строку 2, столбец 2, если 1, квадрат 2x2.

3. проверьте строку 3, столбец 1, столбец 2 и столбец 3, плюс строка 1 столбец 3, строка 2 столбец 3, если 1, 3x3.

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

5. В конце ряда переходите к следующему ряду.

6. до конца.

Вы можете Возможно, вы увидите, как они вписываются в циклы while и т. д., и как && s можно использовать для проверки нулей, и, посмотрев на это, вы, возможно, также заметите, как это можно ускорить. Но, как уже упоминалось в другом ответе,