Задача D. Digital circuit

Автор:A. Baranov   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Имеется прямоугольное ASCII-изображение цифровой схемы, состоящей из логических элементов и связывающих их проводов.

Логические элементы представлены как прямоугольные области, обрамленные рамкой из символов '#' (ASCII 35).

Внутри каждой рамки обязательно содержится описание из цифр и строчных символов латинского алфавита.

Описание может быть разбито на части, разделенные пробелами либо разнесенные по разным строкам.

Провода обозначены в виде последовательностей из символов '.' (ASCII 46).

Оставшееся свободное пространство схемы заполнено пробелами.

Рамки никаких двух элементов не могут стыковаться между собой (между ними всегда имеется зазор).

Провода могут стыковаться между собой только под углом в 90.

Параллельные провода не могут идти вплотную друг к другу (между ними всегда имеется зазор).

Элемент считается подключенным к проводу, если их символы
стыкуются в вертикальном либо горизонтальном направлении.

Провод не может пройти через занятую элементом область.

Шина это набор связанных между собой проводов.

На заданном изображении требуется выделить набор логических элементов и связанных с ними шин.

Формат входных данных

Входные данные содержат ASCII-изображение.

Формат выходных данных

Выходные данные должны содержать количество логических элементов N,
за которым следует N строк, содержащих описание одного элемента в каждой строке.
Части описания должны быть разделены пробелами.

Порядок элементов в списке должен соответствовать порядку,
в котором они встречаются на исходном изображении
при его обходе построчно от левого верхнего угла.

Далее указывается число шин M, за которым следуют наборы
подключенных к ним элементов.

В начале каждого набора указывается число его элементов,
затем следуют их номера
(начиная с нуля).

Ограничения

Общее количество символов изображения не превосходит 106.

Примеры тестов

Стандартный вход Стандартный выход
1
           #####        
#######    #abc#        
# xyz #    #123#        
#     #....#####   #####
#######    .       #   #
           .    ...#abc#
............    .  #   #
.               .  #####
. ############  .       
. #  123     #  .       
. #    xyz   #........  
. ############       .  
.         .          .  
...........          .  
          .    #########
          .....#  abc  #
 #######  .    #########
 #xyz  #...             
 #     #  .       ##### 
 # abc #  ........#123# 
 #######   .      ##### 
           #####        
           #xyz#        
           #####        
8
abc 123
xyz
abc
123 xyz
abc
xyz abc
123
xyz

3
6 0 3 4 5 6 7
3 2 3 4
2 0 1

0.119s 0.030s 15