problema/wall-e

Walle

Scrie aici despre problema/walle

== include(page="template/taskheader" task_id="walle") ==
 
Roboţelul WALL-E este captiv într-un labirint dreptunghiular de dimensiuni $*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 exact $T$ seconde,
* $'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ă $(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 sa stânga, pe care le poate accesa. De asemenea, roboţelul *NU* se poate deplasa în afara labirintului decât prin intermediul celulei 'EXIT'.
 
h2. Cerinţă
 
Comportamentul haotic al portalurilor îl îngrijorează pe WALL-E, astfel că îşî 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*.
 
h2. 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.
 
h2. 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.
 
h2. Restricţii
 
* $1 ≤ N, M ≤ 500$
* $0 ≤ T ≤ 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 vecină care poate fi accesată
* Pentru teste în valoare de 19 puncte labirintul va conţine cel mult 6 portaluri şi $T = 0$
* Pentru alte 19 puncte $1 ≤ N, M ≤ 50$, labirintul va conţine cel mult 6 portaluri şi $T = 0$
* Pentru alte 27 puncte $1 ≤ N, M ≤ 50$, labirintul va conţine cel mult 6 portaluri
* Pentru alte 10 puncte $T = 0$
 
h2. Exemplu
 
table(example). |_. walle.in |_. walle.out |
| 5 12 3
.....#P..E..
..P..###....
.....+...P..
..W...##....
............
| 5
|
| 5 12 3
......P#.E..
..P..###....
.....+...P..
..W...##....
............
| 12
|
| 1 6 3
EPPPWP
| -1
|
 
h3. Explicaţii
 
În primul exemplu, 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.
 
În al doilea exemplu, WALL-E va merge către EXIT, evitând portalurile şi uşa, pe drumul cel mai scurt.
 
În al treilea exemplu, 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)$.
 
== include(page="template/taskfooter" task_id="walle") ==
 

public

task: walle