Autopista The Walking Dead

Para que me conozcan un poco, les comento que mi serie favorita es The Walking Dead. Tiene de todo, suspenso, acción, aventura, terror, romance, gran cantidad de difíciles decisiones moralmente comprometedoras, y lo mejor de todo, zombis.

Para los que también siguen esta gran serie, les será familiar la escena de una carretera con autos abandonados que los personajes deben atravesar para llegar a su destino. Al ver esto, no puedo evitarme preguntar si tuvieran un mapa de la carretera y una computadora cuánto se les facilitaría el viaje en auto. Por esto decidí implementar el algoritmo, ya saben, para estar preparado para el apocalipsis zombi.

Representaremos una carretera de 4 carriles con una matriz de 4 filas por n columnas. Las posiciones dónde exista un auto tendrán un carácter * y las posiciones libres tendrán un carácter de espacio. El viaje se lo realizará en auto, éste puede moverse, después de algunas maniobras, a cualquiera de las 8 posiciones adyacentes, siempre y cuando estén libres. El objetivo es recorrer la carretera de izquierda (columna 0) a derecha (columna n-1).

Representación de Autopista con Salida

Para estar seguro de tener toda la información el sistema debe responder

1. Si se puede llegar al destino o no.
2. De no ser posible indicar hasta qué columna se puede llegar en auto.
3. Indicar el primer camino encontrado.
4. Indicar el mejor camino.
5. Indicar cuántos movimientos se hicieron en total para hallar el primer camino.
6. Una vez encontrado el mejor camino, indicar hasta qué columna se podría llegar con combustible suficiente para m movimientos.