El cavall afamat P17866

Un cavall es troba sobre un tauler d’escacs. El cavall només es pot moure segons les regles habituals (és a dir, modificant en dues unitats una de les seves coordenades, i en una unitat l’altra coordenada, per a un total de vuit possibles moviments), sempre que no surti del tauler ni visiti cap casella amb un obstacle. Quin és el mínim nombre de passos que ha de fer per arribar a una pastanaga?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de files f i el nombre de columnes c del tauler. Tant f com c estan entre 3 i 200. Segueixen f files amb c caràcters cadascuna. Una ‘p’ indica una pastanaga, una ‘X’ indica un obstacle, i un punt indica una posició lliure. Cada cas acaba amb la posició (fila i columna) inicial del cavall. La casella més a l’esquerra de la primera fila és la (1, 1). La posició inicial sempre està lliure.

Sortida

Per a cada cas, si el cavall pot arribar a alguna pastanaga, escriviu el mínim nombre de passos. Altrament, escriviu “no”.