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 $\vert a - c \vert + \vert b - d \vert$. Por ejemplo, la distancia entre $(2, 8)$ y $(5, 1)$ es $\vert 2 - 5 \vert + \vert 8 - 1 \vert = 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:

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

• Test2:

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

• Test3:

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

• Test4:

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

[3]