Enunciado:
Bob es un especialista de programación en juego de estrategias. En su nuevo juego “Edificio en la ciudad” el ambiente de juego es el siguiente: una ciudad se construye por zonas, en los que hay calles, árboles, edificios y fábricas. Todavía hay espacio en el área que está desocupado. La tarea estratégica de su juego es ganar la mayor cantidad de dinero en alquiler de estos espacios libres. Para ganar dinero hay que construir y alquilar edificios y sólo pueden ser de forma rectangular y lo mas amplio y grande posible. Bob está tratando de encontrar una manera de construir el edificio más grande posible en cada área. Pero él viene a través de algunos problemas:
No está permitido destruir edificios ya existentes, árboles, calles y fábricas en la zona de construcción. Cada zona tiene su anchura y longitud. El área se divide en una rejilla de cuadrados de unidades iguales. El alquiler pagado por cada unidad en la que usted está edificio es de 3 $.
Su tarea es ayudar a Bob resolver este problema. La ciudad entera se divide en K áreas. Cada una de las áreas es rectangular y tiene un tamaño de red diferentes con su propia longitud M y N.
La anchura de las unidades ocupadas están marcados con el símbolo R. Las unidades desocupadas están marcados con el símbolo F.
Entrada:
La primera línea de la entrada contiene un entero K - determina el número de conjuntos de datos.
Las siguientes líneas contienen descripciones de la zona. Una descripción se define de la siguiente manera: La primera línea contiene dos enteros zona longitud M <= 1000 N y la anchura <= 1000, separados por un espacio en blanco. La próxima M N líneas contienen símbolos que marcan el reservado o unidades de red libre, separadas por un espacio en blanco. Los símbolos utilizados son: R - unidad reservados F - libre unidad En el final de cada área de la descripción hay una línea de separación. Salida:
Para cada conjunto de datos definidos en la entrada, imprimir en lineas separadas en la salida, el número entero que representa el beneficio obtenido por levantar el edificio más grande en el área codificada por el conjunto de datos.
Ejemplo
Entrada:
2
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
5 5
R R R R R
R R R R R
R R R R R
R R R R R
R R R R R
Salida:
45
0
NOTA: Este ejemplo lo que muestra es que se van a evaluar dos casos, el primer caso es una matriz 5 por 6 y el segundo caso una matriz 5 por 5.
En la salida, la primera linea muestra el edificio mas grande que se pudo construir en la matriz 5 por 6.
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
El total de F (areas disponibles) que forma el mayor rectangulo o cuadrado fueron 15. Cada F tiene un valor de 3$. 3$ por 15 igual a 45. La segunda linea muetra que no se encontro lugar donde construir pues no habia F. 3$ por 0 igual a 0.
Posible Solución: Juego de la Ciudad - ANSI C
lunes, enero 19, 2009
Suscribirse a:
Comentarios de la entrada (Atom)
2 comentarios:
Epale mano... wao... tengo varios dias dandole mente a este problemita y no habia podido dar con el... hasta ahora solo he encontrado un solo error... si resuelvo un problema con k=1, m x n= 2 x 2 y lleno la matriz con F F en la primera linea y R R en la segunda... me debe de dar 6 pero da 3. Despues todo esta super hasta ahora. Podrias compartir conmigo como hiciste el algoritmo?
Si, habia una sutil falla. Gracias por la observacion. Ya lo corregi,,,estaba fallando en par comparaciones. Si gustas puedes probar el programa nuevamente
En cuanto al modo de hacerlo, fue facil. Buscaba primero un lote vacio, y luego buscaba el cuadrado mas grande que se formara apartir de el de lotes vacios...al encontrarlo, me desplazaba tanto vertical como horizontalmente asumiendo que dicho cuadrado hacia parte de un rectangulo aun mas grande...eso era todo!!!
Publicar un comentario