Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | parcare.in, parcare.out | Sursă | Autumn Warmup 2006 |
Autor | Vlad Saveluc | Adăugată de | |
Timp execuţie pe test | 0.175 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Parcare
Pentru a face rost de bani, Cezar s-a angajat, pe perioada verii ca administrator al unei parcari. Parcarea este un patrat format din blocuri de beton, de asemenea patrate, cu latura de un metru. Parcarea are o singura iesire pe latura dinspre nord, in rest este inconjurata de ziduri pe care masinile nu le pot depasi. Masinile din parcare sunt dreptunghiuri cu latimea de 1m si lungimea mai mare sau egala cu 2m. Ele sunt orientate nord-sud sau est-vest. Atunci cand s-a angajat, Cezar nu credea ca aceasta slujba ii va crea probleme, dar astazi este intr-o situatie delicata : un client i-a cerut sa-i scoata masina din parcare. Cezar are cheile de la toate masinile, dar nu este un sofer foarte bun : el nu poate lua viraje, poate merge doar inainte si in marsarier. A incercat timp de o ora sa scoata masina din parcare, dar nu a reusit si s-a gandit sa apeleze la ajutorul vostru. El a facut o harta a parcarii : a reprezentat cu '.' portiunile de asfalt, cu '#' zidurile parcarii si cu litere mari consecutive ale alfabetului latin masinile. Masina care trebuie scoasa din parcare a reprezentat-o cu 'A'.
Cerinta
El va roaga sa-i scrieti un program care sa scoata masina din parcare in mai putin de 100 miscari. El considera o miscare mutarea unei masini, intr-o anumita directie, cu un numar intreg de metri.
Date de Intrare
Pe prima linie a fisierului parcare.in se afla un numar intreg N reprezentand dimensiunea hartii. Pe urmatoarele N linii se afla cate N caractere reprezentand codificarea hartii.
Date de Iesire
Pe prima linie a fisierului parcare.out se va afla numarul de miscari M prin care a fost rezolvata problema. Pe urmatoarele M linii se vor afla 3 caractere ce reprezinta o mutare. Primul reprezinta litera asociata masinii ce va fi mutata, al doilea directia in care va fi mutata (N- nord, S-sud, E-est, V-vest), iar al treilea numarul de blocuri cu care va fi mutata. In locul miscarii prin care masina `A' paraseste parcarea se va afisa `Exit'.
Restrictii si precizari
- 7 ≤ N ≤ 9
- Sunt maxim 10 masini in parcare.
- Pe a doua linie a fisierului de intrare se va gasi un caracter '.' (iesirea)
- Daca o masina are o anumita litera a alfabetului atunci exista exact o masina atribuita fiecarei litere mai mici decat litera respectiva.
- Nu exista doua masini cu aceeasi litera.
- Este imposibil ca alta masina sa poata parasi parcarea inaintea masinii 'A'
- Se garanteaza existenta unei solutii.
- Orice solutie cu mai putin 100 miscari va primi punctajul maxim.
Exemple
parcare.in | parcare.out |
---|---|
8 ###.#### #..BBBC# #..A..C# #..A..C# #.....C# #.....C# #......# ######## | 3 CS1 BE1 Exit |
8 ###.#### #HHH.G.# #....GF# #.EEE.F# #..A..F# #B.A...# #BCCCDD# ######## | 8 BN1 CV1 DV1 FS2 GS3 EE2 HE3 Exit |