Квартал без пустырей

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

Градостроитель хочет выбрать самый большой *квадратный* участок, целиком состоящий из единиц.

Найдите длину стороны максимального квадрата из единиц.

Формат ввода

В первой строке даны два целых числа m и n — размеры карты (m строк и n столбцов). Далее идут m строк, каждая содержит ровно n символов 0 или 1 (без пробелов).

Формат вывода

Выведите одно целое число — максимальную возможную длину стороны квадрата, составленного только из 1.

Ограничения

• 1 ≤ m ≤ 200
• 1 ≤ n ≤ 200
• символы карты — только 0 и 1

Пример

Ввод:

4 5
11110
11010
11110
01111

Вывод:

2

Ключевое наблюдение: квадрат из единиц удобно «наращивать» по одному слою. Если в клетке (i, j) стоит 1, то квадрат с правым нижним углом в этой клетке может быть на 1 больше, чем минимальный из трёх соседних квадратов: сверху, слева и по диагонали сверху-слева. Если хотя бы один из них маленький, больший квадрат всё равно не соберётся (в одном из направлений не хватит единиц).

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

• если grid[i][j] = 0, то dp[i][j] = 0;
• если grid[i][j] = 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

Ответ — максимум по всем dp.

План решения:

• Прочитать m, n и строки поля.
• Идти по клеткам построчно.
• Для каждой клетки обновлять dp по формуле выше.
• Поддерживать текущий максимум.
• Чтобы экономить память, хранить только одну строку dp (размер n+1) и отдельно «диагональ» из предыдущей строки.

Сложность: O(m*n) по времени, память O(n) (или O(m*n), если хранить всю таблицу).

Частая ошибка: неправильно обновить диагональный элемент при 1D-таблице. Нужна временная переменная: сначала запомнить старое dp[j] (это «сверху»), а «диагонь» брать из значения, которое было dp[j-1] в предыдущей строке.