Дистанционный практикум по программированию

Вам дана карта древнего разрушенного лабиринта. Для удобства она разбита на клетки, каждая клетка содержит один из следующих символов:

·        символом «.» обозначена пустая область;

·        символом «#» обозначена стена лабиринта;

·        символом «W» (заглавная латинская буква) обозначено место обвала потолка лабиринта;

·        символом «@» обозначена точка начала движения;

·        символом «$» обозначена точка конца движения.

Требуется добраться из точки начала движения в точку конца движения за минимальное число шагов, или сообщить, что такого пути не существует. Разрешается переходить из одной ячейки в другую, если у них есть общая сторона. Запрещается пересекать границы лабиринта.

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

В первой строке входных данных через пробел записаны два целых числа W (4 ≤ W ≤ 50) — количество строк карты и H (4 ≤ H ≤ 50) — количество столбцов карты.

В следующих W строках записано по H символов, описывающих карту лабиринта. Гарантируется, что на карте есть точка начала движения и точка конца движения.

В первой строке выведите «YES» (без кавычек), если существует путь по лабиринту от точки начала движения до точки конца движения. Во второй строке через пробел выведите два числа — минимальную длину пути между точкой начала движения и точкой конца движения, затем минимальное количество обвалов, которое нужно на этом пути разобрать.

Если добраться из точки начала движения в точку конца движения нельзя — выведите «IMPOSSIBLE» (без кавычек).