El caballo hambriento P72790

Un caballo se encuentra sobre un tablero de ajedrez. El caballo sólo se puede mover según las reglas habituales (es decir, modificando en dos unidades una de sus coordenadas, y en una unidad la otra coordenada, para un total de ocho posibles movimientos), siempre y cuando no salga del tablero ni visite ninguna casilla con un obstáculo. ¿Cuál es el mínimo número de pasos que debe dar el caballo para llegar a una zanahoria?

Entrada

La entrada consiste en diversos casos. Cada caso empieza con el número de filas f y el número de columnas c del tablero. Tanto f como c són como mínimo 3. Siguen f filas con c caracteres cada una. Una ‘z’ indica una zanahoria, una ‘X’ indica un obstáculo, y un ‘.’ indica una posición libre. Cada caso acaba con la posición (fila y columna) inicial del caballo. (La casilla más a la izquierda de la primera fila es la (1, 1).) La posición inicial siempre estará libre.

Salida

Para cada caso, escribid una línea. Si el caballo puede llegar a alguna zanahoria, escribid el mínimo número de pasos. En otro caso, escribid ‘no’’.

Puntuación

• Test:   Entradas donde f,c son siempre 3.  20 Puntos 

• Test:   Entradas donde f,c están entre 3 y 10.  30 Puntos 

• Test:   Entradas donde f,c están entre 3 y 50.  30 Puntos 

• Test:   Entradas donde f,c están entre 3 y 200.  20 Puntos