walle

Roboțelul WALL-E este captiv într-un labirint dreptunghiular de dimensiuni $N * M$. Analizând harta, WALL-E constată că are de-a face cu un labirint extrem de sofisticat. El reușește să identifice următoarele tipuri de celule: W – celula unde, la început, se află WALL-E, E - celula $EXIT$ care poate fi accesată de WALL-E și care îl poate teleporta pe acesta instantaneu în afara labirintului, într-un loc sigur, . - celule libere, care pot fi accesate de WALL-E, # - celule de tip zid, care NU pot fi accesate de WALL-E, + - celule de tip ușă, care pot fi accesate de WALL-E, dar continuarea deplasării la o celulă vecină se poate face doar după o așteptare de exact $T$ secunde, P - celule de tip portal, care îl teleportează pe WALL-E instantaneu, la întâmplare, într-una dintre celelalte celule de tip portal. Dacă WALL-E accesează o celulă $(x_1,y_1)$ de tip portal, atunci el va fi instantaneu teleportat la o altă celulă $(x_2,y_2)$ de tip portal, iar mai departe el se va deplasa numai într-o celulă vecină cu $(x_2,y_2)$ (nu poate sta pe loc) WALL-E se poate deplasa într-o secundă în oricare dintre cele patru celule vecine: sus, dreapta, jos sau stânga, pe care le poate accesa. De asemenea, roboțelul NU se poate deplasa în afara labirintului decât prin intermediul celulei $EXIT$.

Cerință

Comportamentul haotic al portalurilor îl îngrijorează pe WALL-E, astfel că își propune să afle care este numărul minim de secunde în care, cu certitudine, el va putea părăsi labirintul. Dacă nu se poate determina cu certitudine acest lucru, sau dacă WALL-E nu poate părăsi labirintul, răspunsul va fi $-1$.

Date de intrare

În fișierul text walle.in pe prima linie se află numerele $N$, $M$ și $T$, separate prin câte un spațiu. Pe fiecare dintre următoarele $N$ linii se află câte un șir cu câte $M$ caractere.

Date de ieșire

În fișierul text walle.out se va scrie, pe prima linie, un număr natural reprezentând răspunsul găsit sau $-1$.

Restricții și precizări

• $1 \leq N, M \leq 500$;
• $0 \leq T \leq 1 \ 000$;
• Există o singură celulă marcată cu W;
• Există o singură celulă marcată cu E;
• Numărul celulelor de tip portal este mai mare sau egal cu $2$;
• Se garantează că fiecare celulă de tip portal are cel puțin o celulă vecină care poate fi accesată;
• Pentru teste în valoare de $19$ puncte labirintul va conține exact $2$ portaluri și $T = 0$;
• Pentru alte $16$ puncte labirintul va conține exact $2$ portaluri;
• Pentru alte $19$ puncte $1 \leq N, M \leq 50$, labirintul va conține cel mult $6$ portaluri și $T = 0$;
• Pentru alte $27$ puncte $1 \leq N, M \leq 50$, labirintul va conține cel mult $6$ portaluri;
• Pentru alte $10$ puncte $T = 0$.

Exemplul 1

walle.in

5 12 3
.....#P..E..
..P..###....
.....+...P..
..W...##....
............

walle.out

5

Explicație

WALL-E se va deplasa în $2$ secunde la portalul de la poziția $(2,3)$, care îl va teleporta în cel mai defavorabil caz la poziția $(1,7)$, de unde în $3$ secunde va ajunge la EXIT. Total $5$ secunde.

Exemplul 2

walle.in

5 12 3
......P#.E..
..P..###....
.....+...P..
..W...##....
............

walle.out

12

Explicație

WALL-E va merge către EXIT, evitând portalurile și ușa, pe drumul cel mai scurt.

Exemplul 3

walle.in

1 6 3
EPPPWP

walle.out

-1

Explicație

Să presupunem că WALL-E se va deplasa mai întâi la portalul $(1,4)$. Este incert ca WALL-E să poată ajunge la portalul $(1,2)$, deoarece de la portalul $(1,4)$, datorită comportamentului haotic al portalurilor, se poate ajunge la oricare din celelalte trei portaluri, nu doar la portalul $(1,2)$, iar apoi teleportarea următoare îl va putea reîntoarce pe WALL-E, din același motiv, la portalul $(1,4)$. Analog se va întâmpla dacă WALL-E se va deplasa mai întâi la portalul $(1,6)$.