Copiado al portapapeles
Descripción
Cuadradónia es una ciudad bien organizada. Recibe su nombre debido a la forma cuadrada que tiene vista desde el aire, y debido a su cuadrado sistema de calles. Entre sus habitantes, hay quienes ya se cansaron de que todo esté tan rectilíneo, y son estas mismas personas las que han comenzado a bloquear las esquinas de las calles, ``por un futuro más redondo''.
 |
.png) |
|
Calles horizontales
|
Calles Verticales
|
El sistema de calles presente en Cuadradónia es único. Existen exactamente $N$ calles horizontales y $N$ calles verticales que al intersectarse entre sí resultan en ($N * N$) esquinas. Toda calle horizontal pasa por las demás calles verticales, y toda calle vertical por las demás calles horizontales. En la ciudad, cada calle recibe un número especial que la identifica:
Las calles horizontales han sido numeradas desde $0$ hasta $N-1$, de arriba hacia abajo.
Las calles verticales han sido numeradas desde $0$ hasta $N-1$, de derecha a izquierda.
Para referirse a una esquina, la gente menciona primero el número de la calle horizontal y luego el número de la calle vertical. Por ejemplo, el cruce de la horizontal 5 con la vertical 8 se escribiría simplemente $(5, 8)$.
Debido a los bloqueos, desplazarse por la ciudad ya no es tan simple, y el presidente de la Organización de Ciudadanos Ejemplares, Prudentes y Bondadosos (OCEPB) lo sabe. Él debe trasladarse desde su casa en la esquina $(X_o, Y_o)$ hasta la sede de la OCEPB en la esquina $(X_f, Y_f)$, donde se reunirá con un representante de la Organización de Buenos Individuos (OBI).
Ahora transitar por la ciudad es muy peligroso aún cuando con tu sistema de inteligencia tienes anotados todos los puntos de bloqueo necesitas seguridad.
La seguridad es muy cara por lo que haz contratado a un programador para que halle la ruta mas corta.
Como la seguridad cobra por distancias tu no solo debes indicar si hay HAY RUTA POSIBLE también debes indicar la distancia como se muestra en el ejemplo.
Entrada
La entrada consiste de varios casos de prueba, donde cada caso de prueba tiene varias líneas. A continuación se describe el formato de cada caso:
- En la primera línea se encuentra un único entero $N$ ($1 \leq N \leq 20$) que indica el número de calles verticales y horizontales.
- En la segunda línea se encuentran cuatros enteros $X_o$, $Y_o$, $X_f$, $Y_f$ que denotan la esquina de origen $(X_o, Y_o)$ y la esquina de destino $(Xf, Yf)$. Se garantiza que las esquinas dadas son válidas y que la esquina de origen no es la misma que la de destino.
- A continuación siguen $N$ líneas con $N$ caracteres cada una, indicando la presencia/ausencia de bloqueos en cada esquina de la ciudad. Un carácter \texttt{B} indica que la esquina está bloqueada y un carácter \texttt{L} que una esquina está libre.
La entrada termina cuando $N$ es 0. Este caso no debe ser procesado.
Salida
Por cada caso de prueba: En caso de que exista una ruta sin bloqueos desde el origen al destino, debes imprimir \texttt{HAY RUTA POSIBLE CON DISTANCIA seguido de la distancia. Si fuese imposible llegar o si la esquina de destino/origen está bloqueada, imprime NO HAY RUTA POSIBLE.
Ejemplo Entrada
5 0 1 1 4 BLBLB LLLLL BBBLL LBLBB BBLLB 5 0 1 4 3 BLBLB LLLLL BBBLB LBLLB BBLLB 0
Ejemplo Salida
HAY RUTA POSIBLE CON DISTANCIA 4 HAY RUTA POSIBLE CON DISTANCIA 6