Задача 8. Тяни-толкай

Имя входного файла: standard input

Имя выходного файла: standard output

Ограничение по времени: 5 секунд

Ограничение по памяти: 256 MiB

План лабиринта представляет собой клеточное поле размером N × M. Стены лабиринта

на плане обозначены символом ‘1’. В свободных от стен клетках лабиринта отмечены позиции

кладоискателя (‘*’) и сундука с сокровищами (‘+’), а также позиция, в которую кладоискатель должен переместить сундук (‘х’). Остальные свободные клетки отмечены символом ‘0’.

Кладоискатель перемещается по свободным клеткам лабиринта, включая ту, в которую он

должен поместить сундук, но не может находиться с сундуком в одной клетке.

При перемещении кладоискатель переходит из одной клетки лабиринта в другую, граничащую с исходной по стороне. При этом, если надо, он может передвигать сундук следующим

образом:

1. Чтобы толкнуть сундук, кладоискатель должен стать в соседнюю с ним клетку и сделать шаг в клетку с сундуком. В результате кладоискатель окажется в клетке, где был

сундук, а сундук передвинется на соседнюю клетку в том же направлении. Разумеется,

толкать сундук можно только на свободные клетки.

2. Чтобы потянуть сундук, кладоискатель должен стать в соседнюю с ним клетку и сделать шаг в направлении от сундука. В результате сундук переместится в клетку, где

был кладоискатель, а кладоискатель перейдет на соседнюю клетку в том же направлении. Разумеется, клетка, в которую переходит кладоискатель, должна быть свободна.

Делая шаг в направлении от сундука, кладоискатель не обязан тащить его за собой.

На то, чтобы толкнуть сундук, кладоискатель тратит A энергии. На то, чтобы потянуть

сундук, кладоискатель тратит B энергии. Без сундука кладоискатель перемещается очень

легко и потому энергию не тратит.

Определите, какое минимальное количество энергии потратит кладоискатель, чтобы переместить сундук в заданную точку.

Формат входных данных

В первой строке четыре целых неотрицательных числа через пробел: N, M – размеры

лабиринта, A и B – количество энергии, необходимое, чтобы сдвинуть сундук на одну клетку

от себя или к себе, соответственно, 1 ⩽ N, M ⩽ 50, 1 ⩽ A, B ⩽ 50.

Далее N строк, в каждой из которых M символов – план лабиринта, в котором используются следующие обозначения: символ ‘0’ – свободное пространство, символ ‘1’ – стена,

символ ‘*’ – позиция кладоискателя, символ ‘+’ – позиция сундука с сокровищами, символ

‘x’ – позиция, в которую надо поставить сундук.

Других символов на плане нет, при этом гарантируется, что символы ‘+’, ‘*’, ‘x’ встречаются ровно один раз.

Формат выходных данных

В первой и единственной строке одно целое положительное число — минимальное количество энергии, необходимое для перемещения сундука в нужное место. В случае, если такое

перемещение невозможно, вывести −1.

Примеры

standard input standard output

4 5 1 2

*0000

01000 12

+0110

1000x