← Volver a los ejercicios

Cuando el vértice no es la celda

Un robot que puede pisar hasta k = 2 obstáculos seguidos. Dos programas sobre la misma cuadrícula: uno marca la celda y otro marca la celda junto con la racha. Uno de los dos contesta mal, y la celda (1,3) explica por qué.

1. La cuadrícula y la predicción

Gris: obstáculo. De I a F, pasos mínimos sin pisar más de dos obstáculos seguidos, o −1.

Programa:
¿Qué devuelve este programa?

2. Ejecute

Ámbar: obstáculo ya alcanzado. Borde rojo: la celda que se está mirando.

Cola: vacía
Paso 0 de 0
En el segundo programa la cola guarda triples: la tercera componente es la racha.

3. Las llegadas a la celda (1,3)

Viene deRacha al llegarQué pasa
Es la celda con obstáculo de la fila 1, columna 3: se llega a ella desde (1,2), que es obstáculo, y desde (0,3), que es libre.

4. Por qué falla el primero

5. El costo

¿Cuántos vértices tiene el grafo implícito del segundo programa?
Cada estado se visita a lo sumo una vez y tiene a lo sumo cuatro aristas, así que el recorrido cuesta Θ(m·n·k). Agregar el estado multiplica el trabajo por k + 1, y es lo que hace que el programa conteste bien.

6. Para llevarse

Sin solución aquí. Cambie la regla: el robot puede pisar a lo sumo k obstáculos en todo el recorrido, seguidos o no. ¿Cuál es el estado ahora? ¿Sigue sirviendo marcar (celda, cuenta)? Diga cuántos estados hay y dibuje una cuadrícula de 3 × 3 donde las dos reglas den respuestas distintas.