3975 - Escape from Enemy Territory

Enunciado.

Sí! Después de suficientes Time Limit Exceeded logré violar al juez con una solución que le entró en 9.4 segundos (y seguro que le tuvo que arder).

El problema se divide en tres partes:

1. Encontrar el camino más corto entre una base enemiga y cualquier casilla. Esto se hace con una sola pasada de BFS.

2. Encontrar cuál es el camino entre el inicio y el final que tenga máximo elemento mínimo. Esto es muy parecido al problema 10099 - Tourist guide de la UVa. Yo lo hice con una modificación del algoritmo de Dijkstra, pero en una de las soluciones oficiales de los jueces lo hacen con una modificación lasciva de BFS, difícil de comprender (Es más rápido). Tarea: Imprimir este código y entender por qué carajos funciona.

3. Finalmente, encontrar el camino más corto entre el inicio y el final donde ningún elemento de él sea menor que el número encontrado en el paso 2. Esto se hace con una sola pasada de BFS.

El que quiera ver el código, está en mi repositorio de Github.