Áreas

Karel desea hacer su testamento, hace tiempo compró un terreno el cual desea repartir entre sus descendientes. Para hacer una repartición justa necesita saber el área exacta del mismo.

El terreno de Karel se encuentra separado de los terrenos vecinos por medio de una cerca. Los terrenos, tanto el de Karel como el de sus vecinos, se encuentran representados por áreas de zumbadores contiguos. Dos zumbadores son contiguos si la distancia horizontal o vertical entre ellos es igual a 1 (dos zumbadores en diagonal NO son contiguos).

Las cercas que separan los terrenos están representadas por espacios sin zumbadores.

Dado un mundo rectangular, rodeado en su totalidad por paredes, ayuda a Karel a medir el área total de su terreno. Tu programa deberá dejar un número de zumbadores igual al área del terreno de Karel en la esquina inferior izquierda del mundo.

• Karel tiene 100 zumbadores en la mochila.
• El área del terreno de Karel siempre va a ser menor o igual a 100.
• Karel inicia en algún punto de su terreno.
• Cada terreno está formado por montones de un zumbador contiguos ya sea vertical u horizontalmente.
• La esquina inferior izquierda del mundo no tiene zumbador.
• No importan ni la ubicación ni la orientación final de Karel.
• No hay paredes en el interior del mundo.
• El número máximo de veces que Karel puede avanzar para resolver el problema es igual a 65,000.

Se agradece al Comité Olímpico Mexicano de Informática el permiso para publicar este problema en nuestro sitio; que fue aplicado en el examen nacional de la 11a OMI, celebrada en la ciudad de San Luis Potosí, San Luis Potosí en el año 2005.