Laberinto (3) - Girar P76481

Se te da el mapa de un laberinto, donde las casillas marcadas con un ‘#’ son paredes, y las marcadas con un ‘.’ son espacios vacíos. Partiendo de una casilla inicial vacía A, se te pide que avances un cierto número de pasos $p$ siguiendo el siguiente proceso:

• Empiezas avanzando hacia arriba.

• En cada paso sigues con la dirección que tuvieras en el paso anterior, excepto si hay una pared delante. En tal caso, cambias de dirección, siguiendo el siguiente orden:

  • Si no hay pared a tu derecha (respecto a la dirección a la que avanzas), giras a tu derecha, y avanzas.

  • Si hay pared a tu derecha pero no a tu izquierda, giras a tu izquierda, y avanzas.

  • Si hay pared a tu derecha y a tu izquierda, pero no hay pared detrás, das media vuelta, y avanzas.

Si estuvieras rodeado de paredes, lo cuál solo puede ocurrir en la casilla inicial, te quedas donde estás sin dar ningún paso.

Se te pide que muestres el camino (en concreto, los $p$ primeros pasos) que avanzarías siguiendo este proceso.

Entrada

La entrada consiste de una línea con un número $k\geq 0$, seguido de $k$ casos. Cada caso empieza con una línea con las dimensiones $n$ (filas) y $m$ (columnas) del mapa y el número de pasos $p\le 10000$ a avanzar, seguida de $n$ filas de $m$ caracteres ‘#’ y ‘.’ con la descripción del mapa, y un único carácter ‘A’ con la posición inicial.

Salida

Para cada caso, escribe el mapa marcando con un ‘X’ cada uno de los pasos dados. Fíjate que, en función del caso de prueba, es posible que los pasos pasen por encima del carácter ‘A’. Estudia los ejemplos para resolver posibles dudas. Separa dos casos de pruebas con una línea con 3 asteriscos (***).

Puntuación

• TestA:

  Entradas con $k\le 100$ y $n,m \le 10$, y donde todas las casillas situadas en los bordes del mapa son paredes (#), como el Ejemplo 1.

• TestB:

  Entradas con $k\le 10$ y $n,m \le 200$, con mapas de todo tipo, como el Ejemplo 2.