Solución a “Crucero”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 4
Autor: Saúl Germán Gutiérrez Calderón
Fuente: USACO Enero 2009 Gold

Como se puede notar, al trazar la ruta óptima del crucero se está desperdiciando mucho espacio, y daría lo mismo si expandiésemos la isla para que no se desperdiciara espacio entre la ruta y la orilla de ésta.


Si supiéramos cual es la ruta óptima del crucero para expandir la isla bastaría con hacer un Flood Fill para rellenar los espacios con agua que quedan dentro de la ruta.

Resulta que el flood fill e puede hacer aun sin conocer cuál sería la ruta óptima. Si nos ponemos a hacer todos los tipos de celdas adyacentes a la celda actual en un flood fill, nos toparemos con que solo hay 2 que permiten que la isla crezca y 1 que evita que se expanda. El resto de las celdas adyacentes no nos dice nada acerca de si tenemos que poner algo ahí o no (de momento).

Si se pone un pedazo de isla nuevo en el centro de las figura de abajo, entonces la cosa peligrosa tendría que ser rodeada de alguna manera para poder pasar, lo cual nos llevaría a tomar una ruta mas larga. Por ello, no es una buena idea poner un pedazo de isla ahí.

Si es como la de la figura de abajo,

ambos caminos tienen la misma longitud. Por ello, se puede poner un pedazo de isla ahí y esto nos simplifica el problema.

La ruta óptima no puede pasar por el cuadro del centro ya que esto sería un desperdicio de tiempo, por lo cual podemos expandir la tierra ahí.

Entonces, sólo hay que hacer todas las expansiones de tierra hasta que ya no se pueda más y después de esto se puede hacer una mano derecha para buscar la orilla de la isla que al mismo tiempo será la ruta óptima.

2 Replies to “Solución a “Crucero””

  1. Tengo una duda con esta solución, que ocurre con un caso como este donde la isla esta pegada a la orilla del mapa

    5 5
    …..
    …..
    …..
    ..A..
    ..A..

    Este código seguiría el siguiente camino según lo que entiendo:

    +- – – +
    | . . . |
    | + – + |
    | | A | |
    ++ A+ +

    pero si hay alguna cosa mala, no hay nada que impida a este camino rodear la:

    +- – – +
    | . . * |
    | + – + |
    | | A | |
    ++ A+ +

    Así que mi duda es, ¿no es más corto el siguiente camino?:

    5 5
    …..
    …..
    .+-+.
    .|A|.
    .+A+.

    Este camino según me parece también esta rodeando la isla, y es más corto que el que genera este código. Corrí este código en mi computadora y con este mismo caso y me dio de respuesta 20.

  2. Hola Charly,

    Al escribir el problema le puse que habia que rodear la isla.
    Parecia que con eso implicaba que tenias que darle vueltas a la isla (lo cual no podrias apropiadamente hacer si estuviese pegada a algun lado).

    Debi haber agregado que la isla no puede estar en los limites del mundo porque al ser una isla esta en el mar y el mar siempre rodea a las islas.

Leave a Reply to German Cancel reply

Your email address will not be published. Required fields are marked *