Algoritmos e Estruturas de Dados

Pacman - Sair em Segurança

Estás a jogar Pacman num labirinto onde existem vários monstros. O teu objetivo é alcançar uma das células que ficam na fronteira do labirinto sem nunca ocupar a mesma célula que um monstro.
Em cada turno, fazes um movimento (para cima, para a esquerda, para a direita ou para baixo) e, ao mesmo tempo, os monstros também se movem numa direção.
Se for possível escapar do labirinto em segurança, deves indicar o percurso que podes seguir. Esta estratégia tem de ser viável mesmo que os monstros conheçam o teu plano.
notion image

Entrada

A primeira linha da entrada contém dois inteiros h e w (1 ≤ h, w ≤ 1000), que representam a altura e a largura do labirinto.
As próximas h linhas contêm w símbolos que descrevem o labirinto:
  • . - piso
  • # - parede
  • M - monstro
  • Y - a tua posição inicial

Saída

Na primeira linha deves escrever o número de passos necessários para sair do labirinto ou Impossible caso não seja possível.
Se for viável escapar, a segunda linha deve conter um percurso válido que te permita fazê-lo.

Exemplos

Input

5 8
########
#M..Y..#
#.#.M#.#
#M#..#..
#.######
Output

5
RRDDR

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue