Задача №111546. Лихолесье
Тринадцать гномов и хоббит заблудились в Лихолесье. К счастью, они вспомнили, что Гендальф дал им карту. Но чтобы успеть к логову дракона вовремя, им надо поторопиться. Карта включает в себя N*M квадратов, в каждом из которых нарисован лес, дорога, болото или грязь. Чтобы пройти через дорогу, надо потратить 1 час, через грязь - 2 часа, через лес - 3 часа. Через болото идти нельзя. Пройти можно только в соседнюю клетку. Ходить по диагонали нельзя. При этом нельзя три раза подряд пройти через лес, так как он очень густой и там очень легко потеряться. Вам необходимо написать программу, которая определит минимальное время прохождения маршрута.
Вводится два числа N и M количество квадратов в ширину и в длину (1 ≤= N, M ≤= 30). Затем вводится карта из M строк и N столбцов, на которой B точка в которой сейчас стоят гномы, E точка в которую надо попасть, W дорога, F лес, D грязь, а S болото.
Выведите минимальное время прохождения маршрута.
6 3 WWDFFE DFSFSS BWWWWW
12