Fişierul intrare/ieşire:castel.in, castel.outSursăONI 2007, clasa 10
AutorAdrian VladuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incastel.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content