Monstruos en un mapa (2) P67670

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]