Robots P16248

Se dispone de un tablero n × m donde cada casilla está marcada con una R, I, D, o X. Inicialmente, se coloca un robot en una casilla cualquiera, mirando al norte (N), este (E), sur (S) u oeste (O). Repetidamente, el robot realiza dos operaciones:

• Girar o explotar:
  • Si el robot está en una casilla marcada con una I, gira 90 grados a la izquierda;
  • Si el robot está en una casilla marcada con una D, gira 90 grados a la derecha;
  • Si el robot está en una casilla marcada con una R, no gira (sigue recto);
  • Si el robot está en una casilla marcada con una X, explota.
• Avanzar: El robot avanza una casilla en la dirección en que esté mirando (por supuesto, si no ha explotado previamente).

Escribir un programa que determine si el robot saldrá eventualmente del tablero, explotará, o estará moviéndose por el tablero eternamente.

Entrada

La entrada consiste en un natural t ≥ 0 seguido de t casos de prueba separados por una línea en blanco. Cada caso de prueba consiste en una línea con n y m (ambos entre 1 y 60), seguido de n líneas con m caracteres (R, I, D, o X) cada una. Finalmente, la última línea de cada caso de prueba contiene la fila inicial (un número entre 1 y n), la columna inicial (un número entre 1 y m), y la dirección inicial (N, E, S u O).

Salida

Para cada caso de pruebas, escribir “explota”, “sale”, o “no sale” según convenga.