Velocirráptor en forma P22437

Cuando un velocirráptor no huele sangre humana, aprovecha para hacer un poco de ejercicio y marcar su territorio. En una habitación rectangular $n \times m$ con obstáculos, nuestro amigo empieza a correr intentando mantener la dirección y el sentido de su movimiento mientras le sea posible, dejando un rastro de feromona. Bajo ningún concepto saldrá de la habitación, ni pasará por encima de ningún obstáculo, ni volverá a pasar por una casilla por la que ya haya pasado anteriormente. En esos casos, el velocirráptor girará la dirección de su marcha 90 grados a la derecha. Si, incluso girando esos 90 grados, el velocirráptor no pudiera avanzar, se detendría.

Implementa un programa que escriba las casillas por las que ha pasado el velocirráptor antes de detenerse. El velocirráptor siempre empieza en la posición central de la habitación, moviéndose hacia el norte.

Entrada

La entrada describe una habitación. La primera línea tiene el número de filas $n$ y el número de columnas $m$. Se cumple que $2 < n, m < 200$. Tanto $n$ como $m$ son números impares. Siguen $n$ líneas con $m$ caracteres cada una. Un punto indica una posición por la que se puede pasar. Un asterisco indica un obstáculo. La posición central siempre está libre.

Salida

Escribir el tablero con una ’V’ en cada posición por la que haya pasado el velocirráptor.