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 |
