images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:35:24

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1377. Траляля и Труляля идут в бой

Ограничения: время – 2500ms/5000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11236.gif
"Раз Труляля и Траляля
Решили вздуть друг дружку,
Из-за того, что Траляля
Испортил погремушку, –
Хорошую и новую
испортил погремушку."
Перед боем Траляля и Труляля отправились по домам, чтобы надеть на себя доспехи: крышки от кастрюль, совки для угля, диванные валики и каминные коврики. Они договорились, что ровно в пять часов они выйдут из дома навстречу друг другу и встретятся для боя где-нибудь по пути. Но как ни странно, они прошли весь путь до домов друг друга ни разу не повстречавшись.
Напишите программу, которая вычисляет минимальное время, за которое Траляля и Труляля могли дойти до домов, не встретившись друг с другом, а также максимальное ближайшее расстояние, на котором они могли пройти друг от друга, без ограничений на время пути.
Первая строка ввода содержит два целых числа `N`, `M` (`2\ ≤\ N,\ M\ ≤\ 25`) – размеры леса, в котором живут Траляля и Труляля. Следующие `N` строк ввода содержат по `M` символов – карта леса. Символ 'A' означает дом Траляля, а символ 'U' – дом Труляля. Символ '#' означает препятствие, а символ '.' – свободную клетку. Гарантируется, что существует путь по свободным клеткам от одного дома до другого. При движении героев из клетку в клетку считается, что встреча произошла, если в конце хода они оказываются в одной клетке, или если они движутся из соседних клеток навстречу друг другу. При определении ближайшего расстояния рассматриваются только расстояния между Траляля и Труляля в конце хода. Оба героя могут останавливаться, пропускать ход или проходить по одной клетке несколько раз.
Вывести в первой строке одно целое число `T` – минимальное время путешествия без встречи. Во второй строке вывести путь Траляля в виде последовательности из `T` символов 'N', 'S', 'W', 'E' и '.' ('N' – вверх, 'S' – вниз, 'W' – влево, 'E' – вправо, '.' – пропуск хода). В третьей строке вывести аналогичным образом путь Труляля. Если существует несколько вариантов для путей, то можно вывести любой вариант. В четвертой строке вывести одно вещественное число – максимальное ближайшее расстояние во время путешествия с точностью `10^{-3}`. В четвертой строке вывести путь Траляля, обеспечивающий это расстояние, а пятой – путь Труляля. Если существует несколько вариантов таких путей, максимизирующих это расстояние, то вывести минимальный по времени вариант (можно вывести любой из них). Если не существует способа путешествия без встречи, то в первой и единственной строке вывести число `-1`.

Пример ввода

4 5
.....
.###.
A..#.
....U

Пример вывода

5
EESEE
WWWWN
3.162
...SEE.EE
NNNWWWWSS
loading