e-olymp
Yarışlar

ACM ICPC 2011–2012, NEERC 2011

Электрификация

Елена - технолог Расширенной Цепи Мастерства, и она в настоящее время занята проектированием электрической схемы для системы управления светом в гостиничном номере класса люкс.

Схема будет встраиваться в потолок комнаты. Она будет иметь вид прямоугольной сетки, каждая ячейка которой может содержать лишь один элемент. Далее мы приведем список всех возможных элементов с описанием их функций и символов, которыми они задаются.

'.' - пустая ячейка; не имеет никаких входных или выходных сигналов;

'/' - провод; принимает сигнал из левого нижнего угла и передает его в правый верхний;

'\' - провод; принимает сигнал из левого верхнего угла и передает его в правый нижний;

'X' - пересечение; принимает сигнал из верхнего левого и нижнего левого углов и передает его в нижний правый и верхний правый углы соответственно;

'L' - расщепление провода; принимает сигнал из левого нижнего угла и передает его одновременно в верхний левый и нижний правый углы;

'7' - исключающее или; принимает сигнал из левого верхнего угла и левого нижнего угла и передает XOR этих сигналов в верхний правый угол.

Комната отеля имеет n переключателей и m ламп. Переключатели соединены с n точками потолка с левой стороны схемы, а лампы - с m точками потолка с правой стороны. Задача Елены состоит в создании схемы, соединяющей переключатели и лампы согласно следующему руководству.

Дизайнеры комнаты присвоили каждой лампе некоторый набор переключателей. Лампа должна изменять свое состояние (включиться, если была выключена, и выключиться если была включена) каждый раз, когда переключатель, который к ней относится, меняет свое состояние. Лампа не должна изменять свое состояние, если изменяет свое состояние переключатель, который не относится к этой лампе.

prb2374

Должны выполняться следующие правила соединения проводов:

  • нижняя левая вершина элемента 'L' должна иметь в точности один входной провод. Каждая из остальных двух вершин должна иметь по одному выходному проводу;
  • к верхней правой вершине элемента '7' должен быть подсоединен в точности один выходной провод. К каждой из остальных входных вершин должен подходить только один провод;
  • от каждого переключателя должен исходить только один провод;
  • к каждой лампе должен быть подведен только один провод;
  • каждая точка с левой стороны, не соединенная с переключателем, а также каждая точка с правой стороны, не соединенная с лампой, не должны иметь ни входных, ни выходных проводов;
  • каждая из остальных вершин должна либо не иметь входных и выходных проводов, либо иметь в точности один входной и один выходной провод.

Известно, что схема соединений разработана так, что циклические зависимости невозможны.

Елене задается информация о соединении переключателей и ламп. Помогите ей разработать соответствующую схему.

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

Первая строка содержит два целых числа n и m (1n, m10) - количество переключателей и ламп, расположенных в обустраиваемой комнате.

Каждая из следующих n строк содержит по m символов. j-ый символ i-ой строки показывает, соединен ли i-ый переключатель с j-ой лампой. Цифра 1 означает "соединен", цифра 0 означает "не соединен".

Каждая лампа соединена как минимум с одним переключателем, каждый переключатель соединен как минимум с одной лампой.

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

Первая строка содержит два целых числа h и w, размеры схемы (max(m, n) - 1h1000; 1 ≤ w1000).

Каждая из следующих h строк содержит w символов. Допускаются только символы '.', '/', '\', 'X', 'L', и '7'.

Система должна быть работающей (с точки зрения описанных правил), и удовлетворять соединениям, заданным во входном файле.

Если существует несколько вариантов решения, то следует вывести любой.

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
5 3
101
001
010
001
001
Çıxış verilənləri #1
35 77
\...................................................................../\/\/\/
\\............................................./X7X7\................//\/\/\/
\\\............................................LL/...\/\/\/\/\/\/\/\//....../
\\\\........................................../...................../....../.
\\\\\......................................../...................../....../..
.\\\\\....................................../........../X7X7\./X7X7....../...
..\\\\\..................................../...........LL/...\LL/......./....
...\\\\\................................../.........../................/.....
....\\\\\................................/.........../................/......
.....\\\\\............................../../X7X7X\../................/.......
......\\\\\............................/...LL/./.\7X/\/X7\/X7\/\/\/\/........
.......\\\\\........................../.../.../.../.../.../..................
........\\\\\......................../.../.../.../.../.../
...