Identificador: asma-aq
Descripción
Escaleras es un juego (al que se le han quitado las serpientes) que utiliza un tablero con N cuadros numerados del 1 al N. Un jugador empieza en el cuadro 1 y se mueve hacia adelante de acuerdo al valor de un dado lanzado en cada turno (con valores del 1 al 6). Existen escaleras uniendo pares de cuadrados. Si un jugador cae sobre un cuadrado que tenga una escalera comenzando en ese cuadrado, el jugador es transportado al final de la escalera. Puesto que se han suprimido las serpientes un jugador no puede retroceder. Dados el tamaño del tablero y las posiciones de las escaleras en el mismo, encuentra el mínimo número de tiradas que necesitas para llegar al último cuadro del tablero y así ganar el juego. Nota que aunque en su versión física el tablero se muestra en dos dimensiones, se puede pensar en una sola dimensión.
Tarea
Encontrar el número mínimo de tiradas de un dado requeridas para llegar al cuadro N empezando en el cuadro 1.
Restricciones
El tablero tendrá N cuadros. 1≤N≤10000. Existirán M escaleras: 0≤M≤100. Una escalera está definida por dos números A y B. El número A indica el inicio de la escalera mientras que el B indica el final. Ninguna escalera empezará en el cuadro 1 y no existirán dos escaleras que tengan el mismo cuadro inicial o el mismo cuadro final. Los inicios de las escaleras se deben dar en orden creciente.
Muestra de ejecución
Entrada
Introduce el tamaño del tablero N: 14
Introduce el número de escaleras M: 2
Introduce los cuadros inicial y final de la escalera 1: 2 6
Introduce los cuadros inicial y final de la escalera 2: 7 8
Salida
2
(Explicación: estando sobre el cuadro 1, si sale 6 se avanza al 7 y, puesto que existe la escalera (7,8), se avanza al cuadro 8 automáticamente. Estando ahí, con otro 6 se llega al cuadro final, a saber, el 14).
Prueba tu programa con los datos:
a) N=9876, M=0
b) N=100, M=2
15 35
17 80
c) N=10000, M=7
20 40
25 100
45 105
1002 1451
1003 1281
1282 1345
1346 1726