Pracsiu Dan (dnprx) N x 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 exactTsecunde,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ă(x1, y1)de tip portal, atunci el va fi instantaneu teleportat la o altă celulă(x2,y2)de tip portal, iar mai departe el se va deplasa numai într-o celulă vecină cu(x2,y2)(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ța
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 ≤ N, M ≤ 5000 ≤ T ≤ 1000- 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
19puncte labirintul va conține exact2portaluri șiT = 0. - Pentru alte
16puncte labirintul va conține exact2portaluri. - Pentru alte
19puncte1 ≤ N, M ≤ 50, labirintul va conține cel mult6portaluri șiT = 0. - Pentru alte
27puncte1 ≤ N, M ≤ 50, labirintul va conține cel mult6portaluri. - Pentru alte
10puncteT = 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).