Тридевятом царстве на болоте Кикиморы в венке на праздник Алгоритм победы каждое растение имеет свое сакральное значение. Например, василек олицетворяет красоту и нежность, а…

Давайте решим задачу по поиску наибольшего квадрата, состоящего из одинаковых символов (0 или 1) в двоичной матрице. Эта задача является классической задачей по динамическому программированию, часто называемой задачей о поиске максимального квадрата в двоичной матрице.

Идея решения

Для определения размера наибольшего квадрата для каждого элемента (ячейки) нам пригодится динамическое программирование.

Пусть у нас есть матрица matrix размером h x w, где каждый элемент либо 0, либо 1.

Обозначим dp[i][j] — это длина стороны наибольшего квадрата, который завершается в ячейке (i, j) (то есть этот квадрат должен иметь (i, j) в правом нижнем углу).

Правило вычисления

Если matrix[i][j] == 0 или 1 (это не важно — просто символ), то:

• Если хотя бы одна из соседних ячеек с левой, верхней и диагональной стороны не содержит квадрата такого же размера, то dp[i][j] равно 1 (квадрат из одной ячейки).

• Иначе:

  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  

Это выражение означает, что размер квадрата, завершающегося в (i, j), ограничен минимальным из трех соседних квадратий, плюс один.

Алгоритм

1. Вводим размеры и матрицу.
2. Создаем массив dp такого же размера.
3. Проходим по всей матрице:
   • Если текущее значение равно 0 или 1, вычисляем dp[i][j].
4. Во время вычислений отслеживаем максимум dp[i][j].
5. В конце выводим найденный максимум.

Реализация (на Python)

h, w = map(int, input().split())
matrix = []

for _ in range(h):
    row = list(map(int, input().split()))
    matrix.append(row)

# Создаем массив dp, наполненный нулями
dp = [[0] * w for _ in range(h)]

max_side = 0

for i in range(h):
    for j in range(w):
        if i == 0 or j == 0:
            # На границе размер квадрата равен значению ячейки
            dp[i][j] = 1
        else:
            if matrix[i][j] == matrix[i-1][j] == matrix[i][j-1] == matrix[i-1][j-1]:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            else:
                dp[i][j] = 1
        if dp[i][j] > max_side:
            max_side = dp[i][j]

print(max_side)

Объяснение

• Перебираем каждую ячейку.
• Для ячеек на границе массива dp равен 1, поскольку там не может быть квадрата большего размера.
• Для остальных — используем правило вычисления.
• В конце — выводим максимальный размер квадрата.

Это решение работает за O(h*w) по времени и памяти, что подходит для h, w до 1000.