Capitán Karel

El Capitán Karel tiene un nuevo escudo de limodium para vencer a sus enemigos. El limodium es muy resistente pero muy pesado, para lanzarlo el Capitán Karel requiere de un dispositivo de propulsión auxiliar que se calibra para que el escudo avance exactamente K casillas.

El Capitán Karel tiene el mapa de su siguiente misión. En el mapa se muestra a los enemigos como montones de un zumbador. La energía del dispositivo de propulsión alcanza para lanzar su escudo 1 vez por columna. El Capitán puede elegir desde qué fila lanzarlo y con qué dirección (arriba o abajo). Cuando el Capitán lanza su escudo elimina a todos los enemigos en esa columna que estén en la casilla desde dónde se lanzó el escudo hasta una distancia K en la dirección en que se lanzó (ver ejemplo).

Para optimizar el consumo de energía debes ayudar al Capitán Karel a calcular la K mínima necesaria para poder eliminar a todos los enemigos que aparecen en el mapa.

Escribe un programa que ayude a Karel a calcular la K mínima necesaria para eliminar a todos los enemigos del mapa. Una vez calculada, tu programa debe apagar a Karel en la casilla (K,1).

• Karel puede iniciar en cualquier lugar del mundo y con cualquier orientación.
• El valor mínimo que se puede calibrar en el escudo para K es 1.
• El mundo es rectangular, sin paredes internas. El número de filas es menor o igual que el de columnas.
• Las columnas pueden tener cualquier número de enemigos, desde 0 hasta el alto del mundo.
• Para obtener los puntos, tu programa deberá dejar a Karel en la casilla (K,1). No importan la orientación final de Karel ni los zumbadores que queden en el mundo.

• En un conjunto de casos que valen el 40% de los puntos, habrá siempre 2 enemigos por columna y Karel tendrá infinitos zumbadores en la mochila.
• En otro conjunto que vale 40% de los puntos, puede haber cualquier cantidad de enemigos por columna y Karel tendrá infinitos zumbadores en la mochila.
• En el último conjunto con valor de 20% de los puntos, puede haber cualquier cantidad de enemigos por columna y Karel inicia con 0 zumbadores en la mochila.

Para la columna 4 se requiere una K de 3 (si Karel lanza el escudo desde la posición (4,2) con dirección arriba), para cualquier otra columna basta con una K menor a 3. Por lo tanto la K mínima necesaria es de 3 y Karel debe terminar en la casilla (3,1)

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 18a OMI, celebrada en la ciudad de Toluca, Estado de México en el año 2013.