Тридевятом царстве на болоте Кикиморы в венке на праздник Алгоритм победы каждое растение имеет свое сакральное значение. Например, василек олицетворяет красоту и нежность, а ромашка – солнце, чистоту и верность. На прямоугольном лугу за болотом, который имеет размеры h × w h×w, растут ромашки и васильки. В нашей сказке ромашки обозначаются нулями, а васильки – единицами. Таким образом, мы имеем дело с прямоугольной двоичной матрицей. На празднике Алгоритм победы вам предстоит увлекательная задача – найти размер наибольшего квадрата, составленного из символов красоты и нежности на лугу за болотом Кикиморы. Формат ввода В первой строке вводятся два целых числа h h и w w ( 2 ≤ h , w ≤ 1000 2≤h,w≤1000). В следующих h h строках описывается луг как двоичная матрица. Формат вывода Выведите одно целое число – сторону наибольшего квадрата из символов красоты и нежности на лугу за болотом Кикиморы. Система оценивания Первая группа тестов: h h и w w меньше 100 100 – 40 баллов. Вторая группа тестов: без ограничений – 60 баллов. Пример 1 Ввод Вывод 8 6 0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 3 Пример 2 Ввод Вывод 7 6 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 4 Пример 3 Ввод Вывод 8 8 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Давайте решим задачу по поиску наибольшего квадрата, состоящего из одинаковых символов (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) ```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.