Monstruos en un mapa (2) P67670


Statement
 

pdf   zip

thehtml

Haced un programa que, dados un mapa con monstruos, y unas posiciones inicial y final, diga si es posible ir desde la una hasta la otra sólo con movimientos horizontales y verticales, y manteniendo siempre una distancia de seguridad con los monstruos. Aquí usaremos la distancia Manhattan: dos casillas (a, b) y (c, d) se encuentran a distancia | ac | + | bd |. Por ejemplo, la distancia entre (2, 8) y (5, 1) es | 2 − 5 | + | 8 − 1 | = 3 + 7 = 10.

Entrada

La entrada consiste en diversos casos. Cada caso comienza con el número de filas n > 0 y el número de columnas m > 0 del mapa. Siguen n filas con m caracteres cada una. Un punto indica una posición vacía. Los monstruos se indican con dígitos, letras minúsculas y letras mayúsculas, que codifican la distancia de seguridad mínima que hay que mantener con ellos. Los dígitos (entre ‘1’ y ‘9’) indican distancias entre 1 y 9. Las minúsculas (entre ‘a’ y ‘z’) indican distancias entre 10 y 35. Las mayúsculas (entre ‘A’ y ‘Z’) indican distancias entre 36 y 61. La posición inicial se indica con ‘*’, y la posición final con ‘+’. Siempre hay exactamente uno de cada, y en posiciones no amenazadas por ningún monstruo.

Salida

Para cada caso, escribid “SI” o “NO” dependiendo de si es posible o no llegar a la posición final desde la posición inicial.

Puntuación

  • Test1:  ‍5 Puntos ‍

    Resolver casos con n = 1, como los del ejemplo 1.

  • Test2:  ‍15 Puntos ‍

    Resolver casos donde todas las distancias de seguridad son 1, como los del ejemplo 2.

  • Test3:  ‍30 Puntos ‍

    Resolver casos donde todas las distancias de seguridad están entre 1 y 4, como los del ejemplo 3.

  • Test4:  ‍50 Puntos ‍

    Resolver casos de todo tipo, como los del ejemplo 4.

[3]

Public test cases
  • Input

    1 10
    ....1+*...
    
    1 10
    +..3..*...
    

    Output

    SI
    NO
    
  • Input

    3 4
    ...+
    ....
    *...
    
    3 4
    1..+
    .1..
    *.1.
    

    Output

    SI
    NO
    
  • Input

    4 5
    *..3.
    .....
    .....
    2...+
    
    4 5
    *..3.
    .....
    .....
    3...+
    
    5 12
    ..4........2
    .....4.4....
    +...4.4....*
    ......3.....
    .3........3.
    
    2 7
    +.2.3.1
    1*.....
    

    Output

    SI
    NO
    NO
    NO
    
  • Input

    48 4
    d...
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ...+
    *...
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ....
    ..A.
    

    Output

    NO
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++