Duques, condes y vizcondes
Cuando se proyecta la construcción de una vía de comunicación terrestre, como una carretera o vía férrea, el primer paso (una vez conocidos los puntos que debe unir) es determinar cuál será la ruta exacta por la que va a pasar. La tarea no es nada fácil, pues además de tener en cuenta la orografía del terreno de la que depende el número de puentes y túneles que potencialmente habrá que construir, hay que considerar qué otras carreteras se cruzan en su camino y qué uso se está dando a las tierras que atraviesa.
Cuando en marzo de 1819 se llevó al parlamento británico la propuesta de construcción de la que, a la postre, sería la primera ruta ferroviaria abierta al público en utilizar máquinas de vapor, el proyecto no fue aprobado. El problema fue que la ruta elegida para unir las minas de carbón de la zona de Shildon con Stockton y Darlington atravesaba las tierras del conde de Eldon y unos terrenos donde cazaba el duque de Darlington. Ambos "tiraron de galones" y consiguieron que el proyecto no fuera aprobado por 13 votos.
Dos años después, teniendo presente al conde, al duque y a un vizconde de la zona que podría también hacer fracasar la propuesta, consiguieron proyectar una ruta distinta que satisfacía a todos y, por fin, el 19 de abril de 1821 los promotores tuvieron el consentimiento real para construir el ferrocarril.
Hoy en día, siglos después, encontrar la ruta más corta que no pase por ninguna zona vetada por los nobles de turno debería llevar menos de dos años… ¿o no?
Entrada
La entrada está compuesta por distintos casos de prueba, cada uno representando un área donde hay que planificar la ruta del tren. El área se representa como una rejilla de tamaño Tx×Ty (hasta 100×100) en donde cada celda o bien pertenece a algún noble o bien está libre para su uso.
Cada caso comienza con una línea con los dos valores, Tx y Ty. A continuación aparecen Ty líneas con Tx caracteres. Una N indica que por esa celda no puede pasar el tren, mientras que un . significa que los trenes tienen permitido el paso.
Salida
Por cada caso de prueba se escribirá el número de celdas que la vía tendrá que atravesar para ir desde la esquina superior izquierda (primer carácter de la primera línea) a la esquina inferior derecha (último carácter de la última línea) evitando los terrenos pertenecientes a nobles. Si hay varias rutas posibles, se escribirá la longitud de la más corta. Si no hay ruta posible, se escribirá IMPOSIBLE.
Ten en cuenta que la vía puede construirse de tal forma que desde una celda se pase a cualquiera de las ocho adyacentes.
Entrada de ejemplo
5 4 .NNNN N...N .NNN. ..... 5 3 .NNNN NN... NN...
Salida de ejemplo
6 IMPOSIBLE