Escapa de la mazmorra II

Ogmo ha sido encarcelado en una mazmorra (otra vez). Necesita tu ayuda (otra vez). Claramente, Ogmo tiene muchos enemigos a quienes les gustan las mazmorras.

Crea una función que reciba un mapa de una mazmorra y devuelva una única cadena multilínea que contenga la ruta más corta marcada pasando por la llave hasta la salida, el número mínimo de pasos y la secuencia de escape. Esta vez, para escapar de la mazmorra, Ogmo debe recuperar una llave para abrir la puerta de salida (por si te lo preguntas, Ogmo podría lanzar algunos hechizos sobre la cerradura, pero la puerta de salida está maldita y solo puede abrirse con la llave oculta dentro de la mazmorra).

Ogmo comienza dentro de la mazmorra en la posición indicada con O.
La salida se indica con X. Siempre habrá una salida de la mazmorra y la salida puede estar en cualquier lugar dentro de la mazmorra (no solo en los bordes del mapa).
Para abrir la puerta de salida, Ogmo debe recuperar una llave ~. Siempre habrá una llave en la mazmorra, así que podemos deducir que los enemigos de Ogmo son bastante tontos.
Ogmo solo puede moverse en cuatro direcciones: Derecha R, Izquierda L, Arriba U, Abajo D.
Cada paso que Ogmo deba dar para escapar de la mazmorra debe indicarse en el mapa de solución con 1. Si Ogmo camina dos veces sobre la misma casilla, debemos indicarlo con 2.
Las paredes de la mazmorra se indican con #. Ogmo solo puede moverse por los espacios vacíos " ".
Haz coincidir el diseño multilínea mostrado en el ejemplo y las pruebas.

Ejemplos

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

Consulta la primera parte de este desafío: Escapa de la mazmorra I