Problema 3
El Salto del Caballo
caballo.pas, caballo.c, caballo.cpp

Se dispone de una superficie rectangular “cuadriculada”, es decir, formada por un entramado de posiciones o casillas (como ocurre, por ejemplo, con un tablero de ajedrez). Nos interesa buscar caminos dentro de esta superficie que cumplan ciertas condiciones, teniendo en cuenta que algunas de las casillas no pueden formar parte de dichos caminos (para entendernos, representan obstáculos en la superficie).

Problema
Dada una superficie rectangular de dimensión n×m, realizar un programa que la recorra partiendo de una casilla inicial y llegando a una casilla final según las reglas siguientes:

• Todas las casillas deberán ser visitadas excepto las casillas marcadas como no visitables.
• No se podrá visitar más de una vez cada casilla.
• El salto de una casilla a otra deberá realizarse siguiendo las reglas de movimiento del caballo de ajedrez. Esto es, desde una casilla sólo se podrá avanzar a aquellas resultantes de avanzar una posición en línea recta y otra en diagonal en la misma dirección. El esquema muestra en rojo las casillas accesibles al caballo:
  

El programa deberá calcular la secuencia de casillas visitadas desde la inicial hasta la final. En caso que no exista ninguna solución, el programa debe detectar esta situación e informar.

Entrada
La entrada del programa consiste en una secuencia de líneas, que tendrá el siguiente formato:

• La primera línea contiene la dimensión de la superficie, es decir, el número n de columnas y el número m de filas. Los dos valores son por lo menos 1 y a lo mas 16.
• La segunda línea contiene la posición inicial y la posición final, cada posición siendo dos enteros, la columna y la fila respectivamente. Puedes suponer que las dos posiciones están dentro de los límites de la superficie.
• A continuación, m líneas más. Cada línea representa una fila de la superficie, y contiene n caracteres, uno por columna. Cada uno de estos caracteres puede ser 'V' o 'N', dependiendo de si la posición correspondiente es visitable o no. Los caracteres aparecen separados por un único carácter “espacio”.

A efectos de numeración, debe considerarse que las filas van de 1 a m y las columnas de 1 a n.

Salida
La salida del programa contendrá una línea por cada posición que forme parte del camino encontrado como solución que cumpla las condiciones dadas en el enunciado. Cada posición es un par de enteros: la columna y la fila. La primera posición de la solución será la posición inicial, y la última la posición final.
Si no hay ninguna solución, la salida contendrá una única línea con el texto “INSATISFACTIBLE”. Si existe más de una solución, cualquiera de ellas se considera válida.

Ejemplo