El ratón y el gato P95234

Un ratón y un gato están encerrados en una habitación de dimensiones $f \times c$. Lógicamente, el ratón quiere huir del gato, y el gato quiere acercarse al ratón. Escribid un programa que simule sus movimientos: un paso del ratón, un paso del gato, un paso del ratón, etcètera.

Entrada

La entrada consiste en $f$ y $c$, ambas entre 3 i 30, seguidas de $f$ líneas con $c$ caracteres cada una. Un ‘#’ indica un muro, un punto una posición libre, la ‘R’ la posición inicial del ratón, y la ‘G’ la posición inicial del gato. Suponed que los bordes de la habitación siempre serán muros, y que no habrá ninguna parte de la habitación inaccesible. Al final viene un número $p \ge 1$ que indica el máximo número de pasos que se tienen que dar, ya que si en algún momento el gato alcanza al ratón, se tiene que detener la simulación.

Salida

Escribid $p$ (o menos, si el gato alcanza al ratón) pasos de la simulación, cada una seguida de una línea en blanco. Tanto el ratón como el gato sólo pueden quedarse quietos, o moverse vertical u horizontalmente (nunca en diagonal), sin pasar por los muros. Para decidir a donde moverse, el ratón escoge, de las (como mucho) cinco casillas posibles, aquella que esté a la máxima distancia del gato, medida como el número de pasos que el gato tendría que dar para llegar a esa casilla. Similarmente, el gato escoge la casilla que esté a la mínima distancia del ratón. Para desempatar si hay dos o más casillas igual de buenas, se usa esta precedencia, de más a menos: derecha, abajo, izquierda, arriba, quieto.