eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Гиперкуб

Гиперкуб

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Рассмотрим 4-гиперкуб, известный как тессаракт. Единичный цельный тессаракт представляет собой 4D фигуру, представляющую собой выпуклую оболочку 16 точек с декартовыми координатами (±1/21/21/21/2) - ее вершинами. Она имеет 32 ребра (1D), 24 квадратные грани (2D) и 8 кубических 3-граней (3D) известных как ячейки. Мы будем изучать полые тессаракты и определим тессаракт как границу цельного тессаракта. То есть тессаракс есть объединение 8 цельных кубов (его ячеек) которые пересекаются между собой по 24 квадратным граням , 32 ребрам и 16 вершинам.

Разрежем тессаракт вдоль 17 из его 24 граней так что он все еще остается связанным по 7 граням которые остались неповрежденными. Развернем тессаракт на 3D гиперплоскости путем вращения его образующих кубов вдоль граней, которые остались нетронутыми, пока все его ячейки не окажутся в одной и той же 3D-гиперплоскости. Результат называется 3-сеть тессаракта. Этот процесс называется естественным обобщением разрезания и развертывания 3D куба на 2D плоскости для поучения 2-сети куба, состоящей из 6 квадратов.

В этой задаче Вам дан древовидный 8-поликуб в 3D пространстве известный как октокуб. Октокуб - это коллекция 8 единичных кубических ячеек соединенных друг с другом гранями. Более формально, пересечение каждой пары кубических ячеек, составляющих октокуб, либо пустое, либо точка, либо единичный отрезок (1D), либо единичный квадрат (2D). Данный октокуб является древовидным в следующем смысле. Рассмотрим граф смежности октокуба - граф с 8 вершинами соответствующих его 8 ячейкам. Между парами соседних ячеек в графе смежности существует ребро. Две ячейки октокуба являются смежными если их пересечением является квадрат. Ячейки пересекающиеся по точке или по отрезку не считаются смежными. Октокуб называется древовидным, если его граф смежности является деревом.

Ваша задача состоит в том, чтобы определить, является ли данный древовидный октокуб 3 - сетью тессеракта. То есть может ли этот октокуб, помещенный на гиперплоскость в пространстве 4D, быть сложен в пространстве 4D вдоль квадратов пересечения его ячеек с тессарактом.

Например, посмотрите ниже на левую картинку. Он показывает проволочную рамку древовидного октокуба. Вращайте ячейку GHLKG[1]H[1]L[1]K[1] вокруг плоскости GHLK и ячейку FGKJF[2]G[2]K[2]J[2] вокруг плоскости FGKJ на угол 90 градусов в 4-ом измерении вне оригинальной гиперплоскости. В результате точка G[1] соединится с G[2], а точка K[1] соединится с K[2]. Грань GKK[2]G[2] склеится с гранью GKK[1]G[1]. Результат показан справа. 4-ое измерение ортогонально спроецировано на 3 и показано в перспективе. Точки, которые вышли из исходной гиперплоскости, отмечены полыми точками.

prb7568.gif

Вращаем EFJIE[1]F[1]J[1]I[1] вокруг EFJI и EHLIE[2]H[2]L[2]I[2] вокруг EHLI. Результат показан на рисунке слева. Остальные хода следующие. Вращаем MNOPQRST вокруг MNOP, затем вращаем MNOPQRST и IJKLMNOP вокруг IJKL и вращаем ABCDEFGH вокруг EFGH. Последний шаг - склеивание всех граней вместе для получения тессаракта, который показан справа.

prb7568_1.gif

Входные данные

Первая строка содержит три целых числа m, n, k - ширину, глубину и высоту коробки содержащую заданный октокуб (1m, n, k8). Следующие k групп строк описывают прямоугольные слои коробки с верха вниз. Каждый слой описывается n строками по m символов. Строка содержит символы '.' - пустое место, или 'x' - единица куба. Входные данные гарантированно описывают древовидный октокуб.

Выходные данные

Выведите слово "Yes", если заданный октокуб можно сложить в тессаракт и "No" иначе.

Пример

Входные данные #1
3 3 4
...
.x.
...
.x.
xxx
.x.
...
.x.
...
...
.x.
...
Выходные данные #1
Yes
Источник 2015 ACM NEERC, Semifinals, December 6, Problem H