Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1254. Левый поворот
Кратчайшие пути из одной вершиныОлимпиадные задачи на русском языке
| 17/10/2009 | Региональные отборочные командные соревнования для школьников (I) |
| 06/04/2011 | Занятие 20 (D) |
| 01/12/2012 | Занятие 12 (C) |
| 28/06/2016 | Лето 2016 - 2 (D) |
Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Начинающий автомобилист Фанк боится делать левые повороты. Он хочет найти найти
компромисс между временем поездки и её опасностью.
Фанк разделил карту города на клетки, каждая из которых содержит небольшой прямой участок дороги,
перекресток или бездорожье. В клетку с дорогой, ведущей с севера на юг,
можно попасть только из клеток, расположенных выше или ниже, и выехать только вниз или вверх
без смены направления движения. Аналогично для клетки с дорогой, ведущей с запада на восток,
но допустимыми будут только клетки слева и справа. В клетку с перекрестком можно попасть из
любой соседней клетки (сверху, снизу, слева и справа) и можно выехать также в любую соседнюю клетку,
если такое перемещение является допустимым для соседней клетки. В клетку без
дороги перемещаться нельзя. Перемещение из клетки с дорогой или перекрестком без поворота в соседнюю клетку
Фанк оценил в `A` баллов, перемещение из клетки с перекрестком в соседнюю клетку справа по направлению движения с
соответствующим изменением направления движения – в `B` баллов, слева – в `C` баллов, а
противоположную направлению движения – в `D` баллов.
Напишите программу, которая вычисляет минимальную сложность проезда из одной точки города в другую.
Первая строка ввода содержит шесть целых чисел - размеры города `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 100`) и оценки
сложности маневров для автомобилиста `A`, `B`, `C` и `D` (`1\ ≤\ A\ ≤\ B\ ≤\ C\ ≤\ D\ ≤\ 100`).
Далее следует `N` строк, содержащих по `M` символов – карта города, разделенная на клетки.
Символ '#' означает часть города без дорог, символ '+' – перекресток, символ '|' –
дорогу с двухсторонним движением с севера на юг, '-' – дорогу с двухсторонним движением
с запада на восток. Далее следует две строки, содержащих начальную и конечную позицию автомобиля
и направление его движения в формате `r\ c\ d` (`1\ ≤\ r\ ≤\ N`, `1\ ≤\ c\ ≤\ M`, `d` – символ '<', '>',
'^' или 'v', означающий направление движения влево, вправо,
вверх или вниз соответственно). Начальная и конечная позиция автомобиля расположены на
дороге или перекрестке. Верхний левый угол карты имеет координаты (1,1), правый нижний – координаты (`N,\ M`).
Гарантируется, что существует по крайней мере один способ проезда из начального положения автомобиля в конечное.
Вывести одно целое число – минимальную сложность проезда.
Пример ввода
3 3 1 2 3 3 +-+ |#| +-+ 2 1 v 1 2 <
Пример вывода
11
