| Fişierul intrare/ieşire: | walle.in, walle.out | Sursă | ONI 2019, clasa a 10-a, ziua 1 |
| Autor | Ionel-Vasile Pit-Rada | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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'.
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.
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
- 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
Exemplu
| 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 |
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).
