|
П'ятий тур
Розв’язок задачі відправляти на адресу:
alex@naftobaza.itt.net.ua
до 19.12.2004 р.
Лист повинний містити розв’язок однієї задачі.
Тема листа VIO
Вміст листа
Код учасника ...
Код задачі VIO_5
Мова програмування в якій розв’язана задача ...
Розв’язок задачі розмістити, як вкладений текстовий файл з іменем коду завдання програмного коду розв’язку задачі.
Задача: (100 балів)
Koд: VIO_5
Умова
Тур 5. "Скарбоштовхач".
Якийсь лабіринт є матрицею M x N, деякі клітинки якої порожні, а інші заповнені камінням. В одній порожній клітинці знаходиться скарб, а в іншій - шукач скарбів. Шукач скарбів може пересуватися в сусідню клітинку (сусідніми вважаються клітинки, що межують по стороні), а також пересувати скарб таким чином: потрібно встати в сусідню до скарбу клітинку і штовхнути його. Тоді скарб пересунеться на сусідню клітинку в напрямі, заданому поштовхом (від шукача скарбів до скарбу), а шукач скарбів переміститься в клітинку, де тільки що знаходився скарб. При цьому шукач скарбів і скарб не можуть переміщатися в клітинку, заповнену каменем, за межі лабіринту, а також шукач скарбів не може ставати в клітинку, в якій знаходиться скарб, не штовхаючи його.
Потрібно написати програму, яка визначає послідовність поштовхів і пересувань шукача скарбів, що пересуває скарб до виходу. Оскільки скарб дуже важкий, кількість поштовхів повинна бути мінімальною.
При наявності декількох рішень програма повинна виводити те з них, яке сладається з якнайменшої кількості переміщень.
Вхідні дані
Перший рядок вхідного файлу містить числа М і N (1 <= M, N<= 30). Подальші М рядків містять опис лабіринту. Кожний рядок складається з N символів, що описують клітинки лабіринту: заповнена камінням клітинка позначається латинською буквою 'Х' порожня клітинка позначається символом '.' (ASCII код 46), початкова позиція шукача скарбів - буквою 'Y', початкова позиція скарбу - латинською буквою 'В', вихід - латинською буквою 'T'.
Вихідні дані
Якщо рішення не існує, то файл OUTPUT.TXT повинен містити число 0. Інакше, в першому рядку вихідного файлу повинна міститися кількість переміщень К, а в другому рядку - послідовність К символів, яка визначає дії шукача скарбів. Символи 'w', 'e', 'n', 's' позначають пересування шукача скарбів на захід, схід, північ і південь відповідно, а символи 'W', 'Е', 'N', 'S' позначають поштовхи шукача скарбів у відповідних напрямах.
Приклад INPUT.TXT:
3 3
..У
.B.
TXX
OUTPUT.TXT для прикладу:
5
sWnwS
|