Задача №1920. Квадратик
На клетчатом поле \(N\times N\), некоторые клетки которого закрашены, требуется найти размер максимального квадрата, состоящего из закрашенных клеток.
В первой строке входного файла содержится единственное целое число \(N\) (\(1\le N\le 3\,000\)). В каждой из следующих \(N\) строк содержится по \(N\) символов «#» и «.» (соответствующих закрашенным и незакрашенным клеткам соответственно), описывающих таблицу.
Выведите единственное целое число — максимальный размер полностью закрашенного квадрата.
Каждая программа тестируется на четырёх тестах:
чтобы пройти первый тест, достаточно написать решение, работающее за \(O(N^5)\), чтобы пройти второй, требуется решение уже за \(O(N^4)\), третий — за \(O(N^3)\), четвёртый — за \(O(N^2\log N)\).
За каждый успешно пройденный тест начисляется 25 баллов.
Посылка, набирающая \(x\) баллов по сумме баллов за тесты, считается принятой, если выполняются следующие два условия:
* во-первых, если \(x>25\), должна существовать более ранняя принятая посылка, балл за которую по сумме баллов за тесты равен \(x-25\),
* во-вторых, программа не должна содержать отсечений по \(N\), искусственных замедлений работы и т. п.
Если посылка не принята, через некоторое время после её отправки результат её проверки станет «Дисквалифицирован». Балл за принятую попытку вычисляется как сумма баллов за каждый тест минус 5 баллов за каждую более раннюю дисквалифицированную посылку.
Задача считается решённой, если существует принятая посылка, получившая не менее 100 баллов.
Проще говоря, нужно честно последовательно сдать сначала решение, проходящее только первый тест, затем решение, проходящие первые два теста, затем — все тесты, кроме последнего, и, наконец, решение, проходящее все тесты. При этом допускаются ошибки в программах, уменьшающие балл, но для каждой асимптотики должно быть сдано хотя бы одно своё верное решение.