Pacman — Выбраться безопасно
Вы играете в игру Pacman. Вы находитесь в лабиринте вместе с несколькими монстрами. Ваша задача — добраться до одной из крайних клеток лабиринта, при этом ни разу не оказаться на одной клетке вместе с монстром.
На каждом ходу вы можете перемещаться в одном из направлений (вверх, влево, вправо или вниз), и монстры тоже совершают ход в каком-либо направлении.
Если существует способ выбраться из лабиринта безопасно, необходимо вывести маршрут, по которому вы сможете пройти. Причём стратегия должна сработать даже в том случае, если монстры знают ваш план.
Input
Первая строка входных данных содержит два целых числа
h и w (1 ≤ h, w ≤ 1000), задающих высоту и ширину лабиринта.Следующие
h строк содержат w символов, описывающих лабиринт:.— пол
#— стена
M— монстр
Y— ваше начальное положение
Output
В первой строке выходных данных необходимо вывести количество шагов, чтобы выбраться из лабиринта, или
Impossible, если это сделать нельзя.Если существует решение, во второй строке нужно вывести любой допустимый маршрут.
Examples
Input
5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######Output
5
RRDDRConstraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB