Escapando de las fuerzas imperiales
Nuestros héroes, a bordo del Halcón Milenario y confiando en la pericia de Han Solo, están intentado escapar de las fuerzas rebeldes. Para despistar a las fuerzas imperiales, Han Solo quiere introducirse en un campo de asteroides.
Pero antes de tan arriesgada maniobra quiere saber si, una vez dentro, podrán salir de él o es mejor buscar una alternativa más prudente.
El campo de asteroides es una cuadrícula en el que el Halcón Milenario puede moverse en horizontal y en vertical, pero no en diagonal. Las casillas pueden ser transitables, o estar ocupadas por asteroides inmóviles.
Entrada
Cada caso de prueba comienza con una pareja de números 1 ≤ F,C ≤ 20 indicando, respectivamente, el número de filas y columnas de la cuadrícula que representa el campo de asteroides.
A continuación irán F líneas, cada una con C caracteres. Un asterisco ('*') indica una celda con asteroide, y un punto ('.') indica una celda transitable. El Halcón Milenario entra al campo de asteroides en la celda identificada con la letra S, y necesita salir de él en la celda F. En el mapa, existirá una y solo una de cada una de esas letras y sus celdas deben considerarse transitables.
Ten en cuenta que, gracias al hiperespacio, las celdas S y F pueden estar en cualquier posición, no únicamente en los extremos.
Salida
Por cada caso de prueba el programa escribirá "SI" si es viable que el Halcón Milenario se adentre en el campo de asteroides porque hay al menos un camino desde el punto S al punto F siguiendo las reglas de movimiento de la nave. En otro caso, el programa escribirá "NO".
Entrada de ejemplo
2 2 SF .. 2 3 S*F *.. 3 3 .S. **. F..
Salida de ejemplo
SI NO SI