Вишиванка Антона
У Антона есть большая коллекция различных вишиванок (традиционных вышитых рубашек), каждая из которых обладает различными магическими способностями.
Сила вышиванки определяется ее узором и определяется наибольшим руном, который можно идентифицировать в ней. Узор представляет собой квадратную матрицу размера , состоящую из синих и желтых клеток. Руну размера можно представить как идентичных шахматных доски размера (с синей клеткой в верхнем левом углу), расположенных в форме креста "+" (образованного одной вертикальной и одной горизонтальной линиями) с отверстием в середине. Мы считаем, что руна размера есть в узоре, если и только если мы можем разместить нашу руну на поле так, чтобы синие клетки в руне соответствовали синим клеткам в узоре. Обратите внимание, что не обязательно, чтобы желтые клетки в руне соответствовали; они могут совпадать как с синими, так и с желтыми клетками в узоре.
Вот пример руны размера (четыре узора этой руны помечены зелеными квадратами вокруг них):
Обратите внимание, что любая группа желтых клеток в этом узоре также может быть синей, и руна все равно будет существовать:
Также обратите внимание, что это не руна размера , так как узоры должны быть расположены в форме креста "+".
Антону срочно нужно узнать силу вышиванки перед тем, как надеть ее, но, к сожалению, в то время он был очень занят, поэтому он попросил Чмякса (пока еще не злого) написать программу, которая бы определяла силу вышиванки на основе узора. Однако Чмякс обманул его и, украв что-то важное, убежал. Поэтому сейчас Антон просит вас сделать это.
Входные данные
Первая строка содержит одно целое число — размер данного узора.
Каждая из следующих строк содержит символов, каждый из которых либо '.
', либо '#
', где '.
' представляет желтую клетку, а '#
' — синюю клетку.
Выходные данные
В единственной строке вам нужно вывести силу данного узора.
Обратите внимание, что, если и только если на узоре нет рун, ответ равен .
Примеры
Примечание
Максимальная руна на узоре из первого примера имеет размер :
Руна на узоре из второго примера показана на изображениях в условии. Можно показать, что на ней нет руны размера .
Вот вишиванка из третьего примера:
Вот единственная руна размера , которую можно найти на ней:
Можно показать, что здесь нет рун размера или больше.
В четвертом примере можно показать, что здесь вообще нет рун. Снова обратите внимание, что ответ может быть .
Оценивание
( балла): гарантируется, что ответ не превышает ;
( баллов): ;
( баллов): ;
( балл): ;
( балла): ;
( баллов): дополнительных ограничений нет.