`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Задача Manywires. Проблема переплутаних між собою ізольованих  кабелів що зібрані в довгий пучок, добре відома  любителям електроніки та системним адміністраторам. Добре, коли кожен має свій колір, і легко побачити де який починається i де закінчується. Якщо ж колір однаковий – це справжній квест.

Системний адміністратор  має органайзер (спеціальний жолоб, в який вкладаються кабелі), у якому вони йдуть згори донизу, якимось чином, можливо, переплітаючись. Органайзер має комірки - N по ширині та M по довжині органайзера. Комірки зроблено так, що кабель може з неї йти до  сусідних, але через жодну комірку  їх не може пройти більше двох. Системному адміністратору необхідно віднайти для кожного «вихідного» кабеля його номер серед «вхідних» («вихідні» це ті, які розташовані внизу, «вхiдні» - кабелі вгорі). Кабелі нумеруємо злiва направо.

Технічні умови. Програма Manywires читає з пристрою стандартного введення  у першому рядку число N - кількість комірок в довжину, а в другому M – кількість комірок в ширину  (2 ≤ N,M ≤ 200). Далi N рядкiв, в кожному з яких по M символiв, що задають «мапу» кабелів.

Символ «.» означає, що в данiй комiрцi жоден кабель не проходить. Символ « означає, що дрiт йде вниз i лiворуч, вiдповiдно, «\» - вниз і праворуч, символи «(» та «)» задають «перегин» дроту, коли вiн змiнює напрямок. Крiм того, ще iснує символ «X», що означає перетин кабелів у поточнiй комiрцi. Гарантується, що в першому i останньому рядках схеми органайзера вiдсутнi символи «X», «(», «)». Програма виводить на пристрій стандартного виведення   номер «входу», що  відповідає вихідному кабелю в даній позиції.

Приклад

Введення

5
10
./\./.\/..
(..X../\..

.\(.\(..).
..)\.\\(..
./..\.\\\.

Виведення

1 3 2 5 4

Пояснення до прикладу

Задача Manywires

 

© LIKT 1998-2024