Buscaminas
11a OMI, San Luis Potosí 2006
Descripción
Durante la revolución kareliana, Karel Obregón fue un protagonista importante. En esa época el entonces presidente Porfirio Beepers, ordenó a los militares colocar minas en la huasteca kareliana para impedir la entrada del ejército revolucionario a la capital. El general Karel Obregón fungió como espía para el ejército revolucionario, robando los planos donde las minas fueron colocadas. El general Karel Obregón se ha dado a la tarea de determinar el número de minas contiguas a una cierta posición del mapa.
Problema
Dado un mapa rectangular, limitado en su totalidad por paredes, determinar el número de minas contiguas a cada posición del mapa. Una mina es contigua a una posición si la distancia a dicha posición es igual a 1 ya sea en dirección vertical, horizontal o diagonal.
Un ejemplo de mina y sus posiciones contiguas se muestra a continuación:
Consideraciones
- Karel se encuentra dentro del mapa y desconoce su ubicación y orientación inicial.
- Karel tiene infinitos zumbadores en la mochila.
- Una mina se representa con 9 zumbadores.
- No importa la posición ni la orientación final de Karel.
- No importa el número de zumbadores que queden en la posición donde originalmente existe una mina.
Ejemplo
Mundo de ejemplo
Solución al mundo de ejemplo
Agradecimiento
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.