Problema número 385

La ronda de la noche

Tiempo máximo: 1,000-2,000 sMemoria máxima: 16384 KiB

En Ciudad Decoro les preocupa que los jóvenes se reúnan con sus parejas en la noche, a espaldas de sus padres. Por ello en la última Ordenanza Municipal se ha obligado a que todas las casas tengan un jardín-laberinto para acceder a su puerta principal y que (opcionalmente) se instalen sensores de movimiento en los mismos. Conscientes de la posible dificultad de implantación de la Ordenanza, se ha decidido que todos los jardines-laberinto estén organizados en cuadrículas donde cada casilla está libre, tiene un muro o alberga un sensor de movimiento.

Como no podría ser de otra forma, la plataforma activista #FreeLove va a hacer todo lo posible para evitar que estas nuevas medidas supongan un obstáculo real para el amor. Durante las últimas semanas ha ido investigando y realizando mapas de todos los jardines-laberinto, anotando la posición de los sensores de movimiento. #FreeLove ha detectado que únicamente hay 10 tipos diferentes de sensores de movimiento, etiquetados como CAT-k donde k es un número natural entre 0 y 9. Los sensores captan movimiento en línea recta en las 4 direcciones (norte, sur, este y oeste) y la k de su categoría indica el número de casillas que cubren en cada dirección. De esta manera, un sensor CAT-0 únicamente capta movimiento en la casilla en la que está instalado, mientras que un sensor CAT-2 capta movimiento en su casilla y en 2 casillas en cada una de las 4 direcciones (en total cubre 9 casillas). Sin embargo, lo más interesante que ha descubierto #FreeLove es que los sensores no pueden traspasar los muros del laberinto, así que en ocasiones su alcance en alguna dirección se ve limitado.

Ejemplo esquemático de jardín-laberinto

#FreeLove necesita descubrir cuáles de los jardines-laberinto permiten que un amante vaya de la entrada del jardín a la puerta principal de la casa sin ser descubierto por ningún sensor. ¿Podrías ayudarles a diferenciar los jardines-laberinto impenetrables de aquellos favorables al amor, y en esos casos calcular el mínimo número de casillas que hay que atravesar para llegar de la entrada del jardín a la puerta principal?

Entrada

La entrada comienza con una línea conteniendo el número de jardínes a analizar. Cada jardín comienza con dos números 0 < ancho,alto ≤ 1000 con el ancho y alto del jardín-laberinto en una línea. Le sigue la descripción del jardín en alto líneas de ancho caracteres cada una. Estos caracteres son:

  • '#': Una pared.
  • '.': Una casilla libre.
  • 'E': La casilla donde está la entrada al jardín-laberinto.
  • 'P': La casilla donde está la puerta principal de la casa.
  • k, con 0 ≤ k ≤ 9: Casilla que alberga un sensor CAT-k.

La entrada al jardín y la puerta principal de la casa pueden estar en cualquier parte del jardín, incluidas casillas interiores. Además, nada impide que algún sensor vigile la casilla donde está la entrada al jardín o la puerta principal de la casa, por lo que en esos casos no será posible recorrer el jardín sin ser descubiertos.

Salida

Por cada jardín-laberinto la salida será una línea con el mínimo número de casillas del jardín que hay que atravesar para llegar de la entrada a la puerta principal de la casa sin ser descubierto, o la palabra NO en caso de que sea imposible.

Entrada de ejemplo

3
9 4
........P
..2#.....
E.##..1..
.........
6 4
....#P
..#...
.####.
E....1
10 5
E.........
..........
....2.....
..........
.........P

Salida de ejemplo

12
10
NO