Copiado al portapapeles
Descripción
En los últimos tiempos, el tráfico en la ciudad de La Paz se volvió más caótico de lo esperado,haciendo imposible la circulación tanto para el transporte privado como para el transporte público.
El sindicato P.A.T.I.T.O (Partido Autonomo de Transporte Interno de Trabajadores Obreros)
planteo una solución para reducir la cantidad de territorios que las lı́neas de minibuses recorren
en la ciudad. En este problema no discutiremos la eficiencia o no de esta solución, nuestro
objetivo será ayudar a al ilustre ciudadano de nombre “Botas” a llegar a su destino.
Las lı́neas de minibus están formadas por siglas numéricas de N dı́gitos. Por ejemplo en el caso
que N = 3, algunas lı́neas posibles de minibuses serı́an: 219, 254, 010, 000. Cada lı́nea sólo
puede transitar en su territorio y no intersecta con el territorio de otras lı́neas.
Para poder facilitar a los ciudadanos la memorización de las paradas en las que se hace intercambio de una lı́nea de minbús a otra lı́nea de minibús, se sigue la siguiente regla: Si se puede hacer un intercambio de dos caracteres adyacentes en la sigla de una lı́nea de minibus, se puede hacer un intercambio en esas lı́neas en esa parada de minibuses.
Por ejemplo, si “Botas” quiere partir del minibús de lı́nea 321 y llegar a lal territorio del minibús 213, un posible recorrido podrı́a ser:
321 ⇒ 231 ⇒ 213
Llegando a su destino con 3 minibuses.
Ayuda a botas a cálcular cuántos minibuses debe tomar para llegar a su destino.
Entrada
La primera lı́nea de entrada es un entero N (1 ≤ N ≤ 10) que indica la cantidad de dı́gitos que tendrán las siglas de las lı́neas de minibuses.
En la siguiente lı́nea se leeran las dos siglas de minibuses p y q (|p| = |q| = N ), p es el origen y q el destino donde "Botas " quiere llegar.
SUBTAREAS: (60 puntos) 1 ≤ N ≤ 10
Salida
Imprimir el número de minibuses distintos que “Botas” debe tomar para llegar a su destino.
Ejemplo Entrada
3 321 213
Ejemplo Salida
3