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 | a − c | + | b − d |. 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++