Занятие 12

Вам необходимо разработать один из модулей стратегической игры CIV, который находит оптимальный путь для юнита (unit) между двумя точками на карте. Карта мира разделена на квадратные клетки-участки разного типа. Для прохода по ровной местности юнит тратит 1 единицу движения. При движении по лесу или холмам затраты составляют 2 единицы движения. При движении по горам или джунглям тратится 3 единицы движения. Имеются также клетки (вода), движение по которым запрещено.

Кроме того, имеется сеть дорог двух видов. Если клетки карты соединены обычной дорогой, то юнит на переход из одной клетки в другую затрачивает 1/3 единицы движения. Если клетки соединены железной дорогой, то на переход не тратится ни одной единицы движения. Если клетки не соединены дорогой, то затраты на переход определяются типом клетки, в которую осуществляется переход (тип покидаемой клетки на стоимость перехода не влияет).

В зависимости от типа, юнит может потратить во время каждого хода одну (пешеход), две (всадник) или три (танк) единицы движения. В конце хода юнит может переходить из одной клетки в другую, даже если количество оставшихся единиц движения меньше требуемого для перехода. При этом он теряет все оставшиеся единицы движения, но на движении при следующем ходе это не сказывается. Таким образом, при движении по горам без дорог юнит-пешеход и юнит-танк имеют одинаковую скорость – 1 клетка за ход.

Юнит может ходить по горизонтали, по вертикали и по диагонали в соседние клетки.

Напишите программу, которая рассчитает минимальный (по количеству затраченных единиц движения) путь для юнита на заданной карте.

Во входном файле в первой строке содержится семь целых чисел, разделенных пробелами – размеры карты W и H, координаты начальной клетки `X_1,\ Y_1`, координаты конечной клетки `X_2,\ Y_2` и количество единиц движения `M`, которое юнит может потратить на каждом ходе `(1\ <\ W\ ≤\ 100,\ 1\ <\ H\ ≤\ 100,\ 1\ ≤\ X_1\ ≤\ W,\ 1\ ≤\ X_2\ ≤\ W,\ 1\ ≤\ Y_1\ ≤\ H,\ 1\ ≤\ Y_2\ ≤\ H,\ 1\ ≤\ M\ ≤\ 3)`. Далее следует `H` строк, содержащих по `2*W` символов – карта мира. Каждая пара символов содержит информацию об одной клетке. Запрещенные для движения клетки обозначаются символами ** (две звездочки). Для остальных клеток первый символ ('1', '2' или '3') показывает затраты при движении по данной местности, а второй символ показывает наличие дорог. Символ '.' (точка) означает отсутствие дорог, символ '-' (минус) означает наличие обычной дороги, а символ '=' (равно) – железной дороги. Если в соседних клетках есть отметка '=', то эти две клетки соединены железной дорогой. Если в одной клетке есть отметка '-', а в соседней клетке отметка '-' или '=', то эти две клетки соединены обычной дорогой. В остальных случаях дороги между клетками нет. Координаты (1,1) соответствуют левому верхнему углу карты, а координаты `(W,\ H)` – правому нижнему.

В выходной файл дробь вида `P/3`, если от начальной до конечной клетки можно пройти, затратив только `P/3` единиц движения. Если от начальной до конечной клетки дойти невозможно, то в файл вывести одну строку с сообщением "IMPOSSIBLE".

5 3 1 1 5 3 2
1.2-3-2-3-
1.**3.**2-
1.1.1=2=1=

9/3