Nombre Password [ Regístrate ]

Bajo el volcán (OIE 4 - 2000) - Solución

 

La distribución de lava consiste en poner lava en una determinada zona, y distribuir la lava a todas las zonas colindantes que no tengan lava y cuya altura sea menor. Este proceso se formaliza de manera muy sencilla mediante la recursividad. Por tanto, se empleará un procedimiento recursivo para distribuir la lava, llamado lava.

Para representar el volcán se emplea una matriz bidimensional (volcan). Sobre esta matriz se realizan todas las operaciones. Su tamaño es superior en dos unidades que el volcán más grande posible. Esto tiene un objetivo, y es formar un muro alrededor del volcán (dicho muro se simula marcando los bordes de la matriz con lava). ¿Porque se hace esto? Sirve para que durante el proceso recursivo no haya que comprobar los límites del array. Nunca se intentará distribuir lava fuera del array, pues todos los bordes están premarcados con lava.

Nota: la altura se representa mediante enteros de 1 a 9. La lava se representa con 'X', aunque podía escogerse cualquier otro valor mayor que 9, y luego discriminarlo al escribir la salida.

Observaciones

Este ejercicio se puede observar desde otra perspectiva: la modelización de un problema como un grafo.
La prueba es sencilla:
- los vértices son todos los puntos del volcán, cada uno representado por un par de coordenadas y una altura: (x, y, h). Los puntos con lava también son vértices del volcán que ya se han recorrido y se marcan con un número mayor que la máxima altura permitida, que es 9.

- las aristas: existe una arista A entre dos vértices v1 = (x1,y1, h1), v2 = (x2, y2, h2) siendo A = ((x1,y1, h1), (x2, y2, h2)) si y sólo si h1 (la altura de v1) es estrictamente mayor que h2 (la altura de v2) y además son adyacentes. Un vértice marcado con lava no puede formar parte de una arista.

- Además se trata de un grafo dirigido: Notar que si existe la arista A = (v1, v2) entonces NO existe la arista B = (v2, v1).

Ejemplo:

2 2 3 1 5
3 1 4 2 5
3 1 6 3 6
3 3 6 5 4
4 3 4 5 6

consta de las siguientes aristas:
(1,1,2) (2,2,1)
(2,1,2) (2,2,1)
(3,1,3) (4,1,1)
(3,1,3) (4,2,2)
(5,1,5) (4,1,1)
(5,1,5) (4,2,2)
etcétera.

· La solución propuesta recorre el grafo en profundidad, pero es perfectamente válido hacer el recorrido en anchura. Mediante el empleo de una pila en lugar de una cola en la búsqueda en anchura (detallado en la sección de grafos) se puede implementar el programa sin recursión. La implementación propuesta es recursiva.

· Las estructuras de datos propuestas para este problema difieren de las ofrecidas en la sección de grafos, pero esto es así por pura comodidad y claridad para atacar el problema.

· Nótese que aunque se utiliza la recursividad este problema NO está resuelto con un algoritmo de backtracking.

 

Temas relacionados

Recursividad
Grafos

 

Código

Código fuente en C

Código fuente en Pascal



© (2001-2008) ALGORITMIA.NET - Política de privacidad