| Codeforces Round 556 (Div. 2) |
|---|
| Закончено |
Однажды Алиса делала уборку в своем подвале и заметила кое-что любопытное: бесконечное множество одинаковых деревянных фигур! Каждая фигура была сделана из пяти квадратных плиток, одна из была центральной, а остальные четыре примыкали к ней:
Около кусочков лежала большая квадратная доска. Доска разделена на $$$n^2$$$ клеток, расположенных в $$$n$$$ строках и $$$n$$$ столбцах. Некоторые клетки уже заняты плитками, прибитыми к клеткам. Остальные клетки свободны.
Алиса подумала, сможет ли она заполнить доску полностью, используя найденные фигуры? Конечно, каждая фигура должна покрывать ровно пять ячеек доски, никакие две фигуры не должны перекрываться и ни одна фигура не должна вылезать за пределы доски. Однако доска была слишком большой, и Алиса не смогла покрыть ее вручную. Можете ли вы помочь ей определить, возможно ли полностью покрыть доску фигурами?
В первой строке записано одно целое число $$$n$$$ ($$$3 \leq n \leq 50$$$) — размер доски. В следующих $$$n$$$ строках записано описание доски. В $$$i$$$-й строке ($$$1 \leq i \leq n$$$) записана строка длины $$$n$$$. Её $$$j$$$-й символ ($$$1 \leq j \leq n$$$) равен «.» если клетка в $$$i$$$-й строке и $$$j$$$-м столбце свободна, и равен «#» если она занята.
Гарантируется, что доска содержит хотя бы одну свободную ячейку.
Выведите «YES» если доска может быть полностью покрыта фигурами Алисы и «NO» иначе. Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).
3 #.# ... #.#
YES
4 ##.# #... #### ##.#
NO
5 #.### ....# #.... ###.# #####
YES
5 #.### ....# #.... ....# #..##
NO
Следующие иллюстрации описывают доски из примера и их замощения, если они существуют:
