Escape da masmorra II

Ogmo foi preso em uma masmorra (de novo). Ele precisa da sua ajuda (de novo). Claramente, Ogmo tem muitos inimigos que gostam de masmorras.

Crie uma função que receba um mapa de uma masmorra e retorne uma única string multilinha contendo a rota mais curta marcada passando pela chave até a saída, o número mínimo de passos e a sequência de fuga. Desta vez, para escapar da masmorra, Ogmo precisa recuperar uma chave para destrancar a porta de saída (caso você esteja se perguntando, Ogmo poderia lançar alguns feitiços na fechadura, mas a porta de saída é amaldiçoada e só pode ser destrancada pela chave escondida dentro da masmorra).

• Ogmo começa dentro da masmorra na posição indicada por O.
• A saída é indicada por X. Sempre haverá uma saída da masmorra, e a saída pode estar em qualquer lugar dentro da masmorra (não apenas nas bordas do mapa).
• Para abrir a porta de saída, Ogmo precisa recuperar uma chave ~. Sempre haverá uma chave na masmorra, então podemos deduzir que os inimigos de Ogmo são bastante tolos.
• Ogmo só pode se mover em quatro direções: Direita R, Esquerda L, Cima U, Baixo D.
• Cada passo que Ogmo precisar dar para escapar da masmorra deve ser indicado no mapa da solução com 1. Se Ogmo passar duas vezes pelo mesmo ladrilho, devemos indicar isso com 2.
• As paredes da masmorra são indicadas por #. Ogmo só pode se mover pelos espaços vazios " ".
• Faça o layout multilinha coincidir com o mostrado no exemplo e nos testes.

Exemplos

escape([
  ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
  ["#", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"],
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"],
  ["#", " ", "#", " ", "#", "#", "#", "#", "#", "#"],
  ["#", " ", "#", " ", " ", " ", " ", " ", " ", "#"],
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"],
  ["#", " ", "#", "#", "#", " ", "#", "#", " ", "#"],
  ["#", " ", " ", " ", " ", " ", " ", "#", " ", "#"],
  ["#", " ", "#", "#", "O", "#", "#", "#", " ", "#"],
  ["#", " ", "#", "#", "#", "#", "#", "#", " ", "#"],
  ["#", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"],
  ["#", " ", "#", " ", "#", "~", "#", "#", " ", "#"],
  ["#", " ", "#", " ", "#", "#", "#", "#", "#", "#"],
  ["#", " ", "#", " ", " ", " ", " ", " ", " ", "#"],
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"],
  ["#", " ", "#", "#", "#", " ", "#", "#", " ", "#"],
  ["#", " ", " ", " ", " ", " ", "X", "#", " ", "#"],
  ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
]) ➞
  ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]
  ["#", " ", " ", " ", " ", " ", " ", " ", " ", "#"]
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"]
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"]
  ["#", " ", "#", " ", "#", "#", "#", "#", "#", "#"]
  ["#", " ", "#", " ", " ", " ", " ", " ", " ", "#"]
  ["#", " ", "#", " ", "#", " ", "#", "#", " ", "#"]
  ["#", " ", "#", "#", "#", " ", "#", "#", " ", "#"]
  ["#", "1", "1", "1", "1", " ", " ", "#", " ", "#"]
  ["#", "1", "#", "#", "O", "#", "#", "#", " ", "#"]
  ["#", "1", "#", "#", "#", "#", "#", "#", " ", "#"]
  ["#", "1", "1", "2", "2", "2", " ", " ", " ", "#"]
  ["#", " ", "#", "1", "#", "2", "#", "#", " ", "#"]
  ["#", " ", "#", "1", "#", "1", "#", "#", " ", "#"]
  ["#", " ", "#", "1", "#", "#", "#", "#", "#", "#"]
  ["#", " ", "#", "1", "1", "1", " ", " ", " ", "#"]
  ["#", " ", "#", " ", "#", "1", "#", "#", " ", "#"]
  ["#", " ", "#", "#", "#", "1", "#", "#", " ", "#"]
  ["#", " ", " ", " ", " ", "1", "1", "#", " ", "#"]
  ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"]

# Number of steps to escape from the dungeon: 27
# Escape sequence: ULLLDDDRRRRDDUULLDDDDRRDDDR

Notas

Confira a primeira parte deste desafio: Escape da masmorra I