Лабиринт представляет собой матрицу MxN, некоторые ячейки которой пустые, а остальные заполнены камнями. В одной из пустых ячеек находится клад, а в другой - кладоискатель. Кладоискатель и клад не могут находиться в ячейках, заполненных камнями, за пределами лабиринта, а также одновременно в одной и той же ячейке. Кладоискатель может передвигаться в соседнюю ячейку (соседними считаются ячейки, граничащие по стороне), а также передвигать клад следующим образом: нужно встать в соседней к кладу ячейке и толкнуть его. При этом клад передвинется на соседнюю ячейку в направлении, заданном толчком, а кладоискатель - в ячейку, где только что находился клад.
Требуется определить последовательность толчков и передвижений кладоискателя, с помощью которой клад можно передвинуть к выходу (выход находится в пустой ячейке). Так как клад очень тяжёлый, количество толчков должно быть минимальным.
При наличии нескольких решений вывести то из них, которое требует наименьшего количества перемещений.
X', пустая ячейка обозначается символом '.' (ASCII код 46), начальная позиция кладоискателя - буквой 'Y', начальная позиция клада - латинской буквой 'B', выход - латинской буквой 'T'.
NO'.
Иначе в первой строке выходного файла содержится слово 'YES',
а во второй строке содержится последовательность символов, определяющая действия кладоискателя. Символы 'w', 'e', 'n', 's' обозначают передвижения на запад, восток, север и юг соответственно, символы 'W', 'E', 'N', 'S' обозначают толчки кладоискателя в соответствующих направлениях.
| INPUT.TXT | OUTPUT.TXT |
3 3 ..Y .B. TXX |
YES sWnwS |