| Fişierul intrare/ieşire: | castel.in, castel.out | Sursă | ONI 2007, clasa 10 |
| Autor | Adrian Vladu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Castel
Inspaimantatorii tai luptatori au rapit-o pe Printesa Ghiocela si au inchis-o in castelul tau de pe varful Muntelui Plesuv. Deoarece esti un geniu malefic, te-ai hotarat sa ii oferi printesei iluzia unei sanse de evadare. Castelul tau are forma unui caroiaj cu M linii si N coloane. Cele MxN celule ale castelului sunt numerotate de la 1 la MxN in ordinea parcurgerii caroiajului pe linii de sus in jos, iar pe aceeasi linie in ordinea coloanelor de la stanga la dreapta.
In fiecare dintre celulele castelului ai pus cate o cheie, mai precis celula i contine cheia cu numarul i. Evident, pentru a intra intr-o camera, printesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o camera printesa se poate deplasa intr-un moment numai intr-una dintre cele maxim patru camere adiacente pe orizontala si verticala, doar daca detine cheia necesara deschiderii sale. Odata ce a intrat intr-o camera si a obtinut o cheie, printesa o pastreaza si poate sa o utilizeze ori de cate ori doreste.
Cerinta
Desi esti convins ca printesa nu va scapa din castel, esti curios sa afli cate dintre cele MxN camere ii sunt accesibile. Date fiind dimensiunile castelului, camera in care se afla initial printesa si cheile necesare deschiderii fiecareia dintre camere, afla raspunsul la aceasta intrebare presanta.
Date de intrare
Fisierul de intrare castel.in contine pe prima linie trei numere naturale M N K separate prin cate un spatiu reprezentand dimensiunile castelului, respectiv numarul camerei in care se afla initial printesa. Urmeaza descrierea castelului. Pe fiecare dintre urmatoarele M linii se afla cate N numere naturale cuprinse intre 1 si MxN reprezentand cheile necesare deschiderii fiecareia dintre camere.
Date de iesire
Fisierul de iesire castel.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul de camere accesibile printesei.
Restrictii
- 1 ≤ M, N ≤ 150
- 1 ≤ K ≤ M*N
- Odata ce printesa a pasit intr-o camera, respectiva camera va ramane pentru totdeauna deschisa.
Exemplu
| castel.in | castel.out |
|---|---|
| 4 3 1 1 1 4 1 6 2 6 9 8 12 10 11 | 7 |
Explicatie
Printesa porneste din camera 1. Aici folosese cheia 1 si intra in camera 4. Se intoarce in camera 1 si descuie camera 2. Foloseste cheia luata din camera 4 si descuie camera 3. In acest moment ea detine cheile 1, 2, 3 si 4. Foloseste cheia 2 si intra in camera 6, apoi foloseste cheia 6 si intra in camera 5, apoi in camera 4, de unde, folosind cheia luata din camera 6 intra in camera 7. La final printesa are cheile 1, 2, 3, 4, 5, 6, 7 si nu mai poate deschide nici o alta camera.
