Doble Laberinto Consideremos un videojuego de aventuras en el que N jugadores, identificados con los valores 1..N, intentan salir de un laberinto. El laberinto está formado por salas y pasillos y posee una única entrada y una única salida. Hay una sala especial inmediatamente después de la entrada y otra inmediatamente antes de la salida. Las salas están identificadas mediante valores naturales mayores que 0, pero su número no está acotado. Cada sala dispone de un cierto número de puertas de entrada y de salida, con propiedades que concretamos a continuación. Cada puerta de salida está dotada de una cerradura, consistente en M valores naturales indexados con los números entre 1 y M. Cada jugador comienza el juego con una llave, que también consiste en M valores naturales indexados con los números entre 1 y M. Decimos que una llave abre una cerradura si para cada índice, el valor correspondiente de la llave es mayor o igual que el de la cerradura. Si un jugador llega a una sala cuyas puertas de salida no puede abrir, dicho jugador se desintegra en esa sala y no puede continuar la travesía del laberinto, aunque sí puede participar en las que se realicen posteriormente. El laberinto se divide en dos partes diferenciadas. En la primera, cada sala tiene una puerta de entrada y dos de salida (denominadas izquierda y derecha). Cada puerta de salida puede dar acceso a un pasillo que lleva a otra sala, o bien no dar acceso a ningún sitio, aunque su cerradura se pueda abrir. Además, cada puerta de salida tiene asociado un contador, representado por un número natural, cuya utilidad se describe más adelante. Existen determinadas salas que marcan un final de la primera parte, a las que nos referiremos simplemente como "salas finales". Dichas salas se caracterizan porque sus dos puertas de salida dan acceso a sendos pasillos que van a la misma sala de la segunda parte, aunque pueden tener distintas cerraduras. Toda sala de la primera parte cumple que de ella sale al menos un pasillo que lleva a otra sala de la primera parte (si salen dos pasillos, han de ser a salas distintas) o bien es final. En cuanto a la segunda parte, cada sala tiene cero, una o dos puertas de entrada (también denominadas izquierda y derecha) y una de salida, con su correspondiente cerradura. Por tanto, puede ocurrir que una sala sea accesible desde cero, una o dos salas. Exceptuando la sala anterior a la salida del laberinto, la puerta de salida de cada sala da acceso a un pasillo que lleva a otra. Para simplificar los cálculos que habremos de realizar, supondremos que el identificador de cada sala final de la primera parte coincide con el de la sala de la segunda parte a la que se accede desde ella. Por lo demás, dentro de la primera parte los identificadores de sala no se pueden repetir, ni tampoco dentro de la segunda parte. Ejemplo de laberinto: los números indican los identificadores de sala y las líneas indican los pasillos. Se sobreentiende que los pasillos que comunican las dos partes son dobles. entrada 6 / \ 14 8 / \ \ primera parte 12 20 5 / \ / 3 \------/ \ / \ -------|-------/---\-------------- | / \ 3 5 \ \ / \ 4 2 20 segunda parte \ \ / 16 9 \ / 7 salida Notad los casos especiales: en la primera parte, las salas finales son la 3, la 5 y la 20; la puerta derecha de la sala 12 y la puerta izquierda de la sala 8 no llevan a ningún sitio. En la segunda parte, solo se puede acceder a la sala 16 por una puerta y a la 2 no se puede acceder. Paso de la primera parte del laberinto: --------------------------------------- Supondremos que antes de comenzar a cruzar el laberinto se realizan unas pruebas de calificación, fuera del objeto de esta práctica, que determinan el orden en que los jugadores intentan pasar la primera parte. Usando el mencionado orden, cada jugador intentará ocupar una sala final a la que pueda llegar (y de la que pueda salir) sin desintegrarse. Si un jugador ocupa una sala final, ésta ya no puede ser ocupada por ningún otro. Durante el recorrido de esta parte del laberinto, cada vez que un jugador llegue a una sala no final con dos puertas que pueda abrir, elegirá aquella que le dé paso a un mayor número de salas finales no ocupadas, independientemente de que se desintegre por el camino a ellas o no. En caso de empate, elegirá siempre la puerta izquierda. Si llega a una sala que no le da acceso a salas finales no ocupadas, el jugador se desintegra en dicha sala, aunque pueda abrir alguna de sus puertas. Los contadores de las puertas de salida han de gestionarse de manera que informen en todo momento del número de salas finales no ocupadas existentes a partir de cada puerta. Si en algún momento se llegan a ocupar todas las salas finales, no podrán participar más jugadores. Esta fase acaba cuando se ocupen todas las salas finales o cuando lo hayan intentado todos los jugadores, lo que ocurra primero. Paso de la segunda parte del laberinto: --------------------------------------- Una vez ocupadas todas las salas finales posibles (no siempre serán todas, pues puede que la mortalidad sea muy alta o que haya relativamente pocos jugadores), cada una por un jugador, éstos comienzan simultáneamente a cruzar la segunda parte. Como hemos dicho, cada sala final de la primera parte da acceso a una sala determinada de la segunda parte, a partir de la cual los jugadores intentan llegar a la salida del laberinto. Notad que, una vez llegados a dicha sala (la de la segunda parte), sólo hay un camino posible hasta la salida y cada jugador puede desintegrarse en él o llegar a la salida, pero no hay opción de probar diferentes caminos. Como restricción adicional, imponemos que de cada sala solo pueda salir un jugador. En las salas a las que puedan llegar dos jugadores, se espera hasta que ambos hayan llegado y se organiza una competición antes de probar sus llaves en la cerradura. El ganador se queda con las llaves del perdedor, de forma que en esa sala, y las siguientes, podrá probar todas las llaves que haya acumulado para abrir las correspondientes cerraduras. La competición entre dos jugadores se basa en determinar cuál de ellos tiene la mejor llave original. Para ello definimos la desigualdad entre dos llaves de la siguiente manera: contamos cuantos índices de la primera llave tienen un valor estrictamente mayor que su correspondiente en la segunda y, análogamente, cuantos índices de la segunda llave tienen un valor estrictamente mayor que su correspondiente en la primera. Si la primera cantidad es mayor que la segunda, diremos que la primera llave es mejor. Si es menor, diremos que la segunda llave es mejor. Si ambas son iguales, diremos que las llaves empatan. En ese caso, consideramos que el ganador es el participante con menor identificador. Ejemplo: sean a = 2 0 1 0 y b = 2 1 1 0. Tenemos que b es mejor que a. Sin embargo, si a = 1 1 2 1 y b = 1 0 1 2 , entonces a es mejor que b. Con todo ello, solo puede llegar a la salida un jugador como máximo. SE PIDE: -------- Diseñar un programa modular razonablemente eficiente que simule la situación arriba descrita. En primer lugar, debe leer la estructura del laberinto y las llaves de los participantes, y realizar todos los procesos de inicialización que se consideren oportunos. Después tendrá que ir procesando las diversas tareas que se le pidan. Estas podrán ser las siguientes: 1) Dada una permutación de los índices de los participantes, que representa el resultado de las pruebas de calificación, calcular si hay alguno que consigue salir del laberinto (comenzando solamente con su llave original). En caso de existir, hay que decir cuál es y proporcionar la lista de las llaves de las que se ha apoderado en la segunda parte del laberinto. Dicha lista aparecerá ordenada de forma lexicográfica de menor a mayor índice y, para cada índice, de menor a mayor valor. Por ejemplo, con M=3, la llave 1 2 1 va antes que la 1 2 3 pero después de la 1 1 3. También se ha de obtener la lista de los jugadores que han podido ocupar una sala final, cada uno acompañado con su correspondiente sala y ordenada de menor a mayor identificador de jugador. Por último, se ha de escribir la lista de las competiciones producidas en las salas de la segunda parte, ordenadas de menor a mayor según el participante de índice más pequeño. Si un participante es el de índice más pequeño en más de una lucha, éstas aparecerán ordenadas de menor a mayor según el participante de índice más grande. Además, se ha de informar del resultado de cada competición y de la sala donde se ha producido. 2) Dado un jugador, averiguar si tiene alguna manera de salir del laberinto si intenta cruzarlo en solitario, es decir, con la posibilidad de probar todos los caminos de la primera parte y sin luchas en la segunda parte. Si puede hacerlo, se ha de informar de la longitud, en número de salas visitadas, de su camino más corto y del identificador de la sala final del mismo. En caso de existir más de una sala posible (es decir, si hay varios caminos de longitud mínima diferentes) se elige la de más a la izquierda respecto a la primera parte. 3) Sustituir el laberinto actual por uno nuevo. 4) Sustituir la llave original de un jugador determinado por una nueva, que pasa a hacer el papel de aquella. Más adelante podremos añadir más consultas a elementos del sistema implicados en los procesos anteriores. La forma de comunicarnos con el programa para que realice dichas tareas será parecida a la de los casos de estudio de teoría: "Cubeta", "Experimentos Inmunológicos", etc. Podéis diseñar un esquema provisional que ya refinaréis cuando conozcáis el juego de pruebas público. En días sucesivos se completarán los detalles que se hayan podido pasar por alto en este enunciado y se publicarán las aclaraciones oportunas. La sintaxis *exacta* de los datos y resultados, acompañada del juego de pruebas público, se conocerá dos semanas antes del día de la entrega del programa C++. Hasta entonces no podréis implementar de forma definitiva las operaciones de lectura y escritura necesarias para los tipos que utilicéis, aunque sí podréis especificarlas. Podéis consultar el ejemplo del cuatrimestre anterior para tener una idea aproximada.