
SAUSAGE	Сосиска SAUSAGE Описание По случаю ввода в строй новой транспортной системы в главном банкетном зале столицы Галактической Республики планируется проведение грандиозного банкета. Главным блюдом банкета будет гигантская сосиска, декорированная в форме древнего туннеля метро. Повара желают сделать сосиску как можно длиннее, но таким образом, чтобы вся она располагалась на столах и не содержала самопересечений и самоналеганий. Задача Ваша задача состоит в том, чтобы написать программу SAUSAGE, которая бы вычисляла максимально возможную длину сосиски и печатала бы оптимальное размещение сосиски на столах. Для простоты предположим, что банкетный зал представляет собой прямоугольник NхМ метров. Каждая секция стола имеет размер 1×1 метр. Столами занята только часть банкетного зала. В каждой секции стола может размещаться единственная секция сосиски (также длиной 1 метр), при этом возможны варианты, перечисленные на рис.1. Сосиска должна пересекать без разрывов границы секций стола и может быть замкнутой. Она должна лежать только на столе Рис.1 Возможные положения секции сосиски на секции стола Формат входных данных Входные данные для вашей программы определяют план банкетного зала и загружаются из файла SAUSAGE.IN. Вначале задаётся два целых числа N и М (1<=M,N<=10), определяющих размер банкетного зала по координате Х и У соответственно. Далее, начиная с новой строки, идут М строк текста, каждая из которых содержит в точности N символов, кроме, возможно, незначащих пробельных символов в конце. Символ Х (заглавная латинская буква "икс") означает, что в данном месте банкетного зала находится стол, а "." (точка) означает, что данная секция банкетного зала свободна. Левый нижний квадрат плана имеет координаты (0,0) Формат выходных данных Первым числом должно файла SAUSAGE.OUT быть целое число - максимальная длина сосиски, которую можно разложить на столах. Далее должны перечисляться координаты секций стола, которые занимает сосиска. Секции стола должны быть перечислены в порядке от одного конца сосиски до другого Например: SAUSAGE.IN 4 4 ХХХХ ..X. XXX. ..X. SAUSAGE.OUT 7 0 1 1 1 2 1 2 2 2 3 1 3 0 3

SAUSAGE

Сосиска
SAUSAGE

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

Задача
Ваша задача состоит в том, чтобы написать программу SAUSAGE, которая бы вычисляла максимально возможную длину сосиски и печатала бы оптимальное размещение сосиски на столах.

Для простоты предположим, что банкетный зал представляет собой прямоугольник NхМ метров. Каждая секция стола имеет размер 1×1 метр. Столами занята только часть банкетного зала. В каждой секции стола может размещаться единственная секция сосиски (также длиной 1 метр), при этом возможны варианты, перечисленные на рис.1. Сосиска должна пересекать без разрывов границы секций стола и может быть замкнутой. Она должна лежать только на столе

Рис.1 Возможные положения секции сосиски на секции стола

Формат входных данных
Входные данные для вашей программы определяют план банкетного зала и загружаются из файла SAUSAGE.IN. Вначале задаётся два целых числа N и М (1<=M,N<=10), определяющих размер банкетного зала по координате Х и У соответственно. Далее, начиная с новой строки, идут М строк текста, каждая из которых содержит в точности N символов, кроме, возможно, незначащих пробельных символов в конце. Символ Х (заглавная латинская буква "икс") означает, что в данном месте банкетного зала находится стол, а "." (точка) означает, что данная секция банкетного зала свободна. Левый нижний квадрат плана имеет координаты (0,0)

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

Например:

SAUSAGE.IN
4 4
ХХХХ
..X.
XXX.
..X.

SAUSAGE.OUT
7
0 1 1 1 2 1 2 2
2 3 1 3 0 3