Pequeño ejercicio sobre un vector simple. Básicamente,se trata de recorrer el vector BOARD desde el principio (posición 0), hasta más allá del final (posción n - 1, siendo n el tamaño del vector), evitando las casillas con obstáculos (que estarán marcadas con un 1).
Empiezas en el índice 0 del vector BOARD (de tamaño n) con un valor dado leap, de forma que i = 0. Está garantizado que BOARD[0] siempre es 0 (los obstáculos se marcarán con un 1). Dada cualquier posición i, es posible moverse de las maneras siguientes:
-
Walk forward: Si i + 1 == 0, entonces puede moverse hacia adelante.
-
Walk backward: Si i - 1 == 0, entonces puede moverse hacia atrás.
-
Jump: si la posición i + leap de BOARD contiene un 0, entonces puede saltar de la posición i a la posición i + leap.
El juego termina cuando se sale del vector, es decir, caminando o saltando se llega a la casilla n o más allá.
El primer dato de entrada es el número de ejercicios, en su propia línea. A continuación, el algoritmo leerá el tamaño del vector y el dato leap en una línea separados por un espacio, mientras que en la siguiente línea aparecerán los unos y ceros que constituyen las posiciones del vector, también separados por espacios.
El archivo de entrada es data.txt. Por ejemplo:
1
10 3
0001100011
Si un determinado juego puede ganarse, entonces se muestra "YES" en una sola línea. En caso contrario, se muestra "NO". En el caso explicado en el formato de entrada, la salida sería:
YES
En el caso explicado en la sección de formato de entrada, tendremos un vector de 10 posiciones, y una capacidad de salto de 3 casillas.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
El proceso de juego es el siguiente:
-
Caminamos hasta la casilla 2, dado que en la 3 hay un 1.
0 1 2 3 4 5 6 7 8 9 0 0 * 1 1 0 0 0 1 1 -
Saltamos a la casilla 5, puesto que saltamos de 3 en 3 casillas.
0 1 2 3 4 5 6 7 8 9 0 0 0 1 1 * 0 0 1 1 -
Caminamos hasta la casilla 7, dado que en la 8 hay un 1.
0 1 2 3 4 5 6 7 8 9 0 0 0 1 1 0 0 * 1 1 -
Saltamos a la casilla 10, que está fuera del vector (el final es la casilla 9), y por lo tanto termina el juego.
Para resolver este ejercicio, es posible aplicar una estrategia eager, o una estrategia más compleja, de backtracking. Explora las ramas de este repositorio para las soluciones correspondientes a estas estrategias.