Nombre Password [ Regístrate ]

Bajo el volcán (OIE 4 - 2000)

 

Se desea simular el desplazamiento de la lava de un volcán a lo largo de la ladera del mismo. Representamos la ladera por una superficie rectangular cuadriculada. Para cada casilla de esa superficie conoceremos su altura respecto el nivel del mar.

El comportamiento de la lava se rige por las siguientes reglas:

1. La lava fluye desde la casilla en la que está situada el cráter del volcán.
2. Dado un punto alcanzado por la lava, ésta fluye a todos los puntos adyacentes al mismo (los 8 vecinos que estén dentro de los límites de la superficie) que se encuentren a una altura estrictamente menor.

Objetivo

Se pide confeccionar un mapa de la ladera del volcán que identifique los puntos alcanzados por la lava.

Entrada

La entrada del programa consiste de una secuencia de líneas, que residen en un archivo de texto (ASCII) con nombre VOLCAN.DAT, que tendrá el siguiente formato:

· La primera línea (la 1) contiene el número de filas (m) y columnas (n) de la ladera. Podéis suponer que se cumple 1 <= m < 100 y 1 <= n < 100.

· La segunda línea (la 2) contiene la coordenada (i, j) del cráter, 1 <= i <= m y 1 <= j <= n.

· Las m líneas siguientes (de la 3 a la m+2) contienen, cada una, una fila de la ladera. Cada punto de esa fila contiene un número positivo entre 0 y 9, que representa la altura de ese punto. Los números están separados por un único blanco.

Salida

La salida del programa ha de grabarse en un archivo de texto (ASCII) con nombre VOLCAN.RES, con una secuencia de m líneas que contienen, cada una, una fila de la ladera, cuyo valor para cada punto será: la letra 'X', si el punto ha sido alcanzado por la lava; el mismo valor que en la entrada, si el punto no ha sido alcanzado por la lava.

Ejemplo de entrada

5 5
3 3
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

Ejemplo de salida

2 X X X 5
3 X X X 5
3 X X X 6
3 X 6 X X
4 X X 5 6



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