El gusano viajero P46641

Un gusano se desplaza por un tablero $n \times m$, manteniendo la dirección y sentido de su movimiento mientras le sea posible. El gusano no puede salirse del tablero, ni pasar por encima de ningún obstáculo, ni pasar por una casilla por la que ya había pasado anteriormente. En esos casos, el gusano gira la dirección de su marcha 90 grados a la derecha. Si, incluso girando esos 90 grados, el gusano no pudiera avanzar, se detiene.

Implementar un programa que escriba las casillas por las que ha pasado el gusano antes de detenerse. El gusano empieza en la posición central del tablero, moviéndose hacia arriba.

Entrada

La entrada consiste en la descripción de un tablero. La primera línea contiene el número de filas $n$ y el número de columnas $m$. Tanto $n$ como $m$ son números impares mayores que 2. Siguen $n$ líneas con $m$ caracteres cada una. Un ’.’ indica una posición por la que se puede pasar. Un ’*’ indica un obstáculo. La posición central siempre está libre.

Salida

Escribir el tablero con una ’G’ en cada posición por la que ha pasado el gusano.