Республиканская олимпиада по информатике 2014 год, Усть-Каменогорск

Задача C. Максимальный квадрат

Ограничение по времени:

15 секунд

Ограничение по памяти:

128 мегабайт

Дана матрица размера $N \times M$ состоящая только из нулей и единиц. Нужно найти наибольшую квадратную подматрицу, в сторонах которой только единицы.

Формат входного файла

Первая строка входного файла содержит два целых числа $N$ и $M$. Следующие $N$ строк содержат по $M$ цифр 0 и 1, разделенных пробелом. Если таких квадратов нет, выведите 0.

Формат выходного файла

Выведите одно целое число -- размер максимального квадрата, в сторонах которого только единицы.

Примеры:

Вход

4 5
01111
01011
11001
11111

Ответ

4

Вход

2 3
000
000

Ответ

0

Вход

3 3
011
011
010

Ответ

2

Замечание

Подзадача 1 — 30 баллов ($1 \le N, M \le 100$) Подзадача 2 — 29 баллов ($1 \le N, M \le 300$) Подзадача 3 — 41 баллов ($1 \le N, M \le 1500$)