castel

Time limit: 0.05s Memory limit: 2MB Input: castel.in Output: castel.out

Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.

Castelul tău are forma unui caroiaj cu MM linii şi NN coloane. Cele MxN celule ale castelului sunt numerotate de la 11 la MNM \cdot N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta.

În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula ii conţine cheia cu numărul ii. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maxim patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale.

Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte.

Cerinţă

Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele MNM \cdot N camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.

Date de intrare

Fişierul de intrare castel.in conţine pe prima linie trei numere naturale MM, NN, KK separate prin câte un spaţiu reprezentând dimensiunile castelului, respectiv numărul camerei în care se află iniţial prinţesa. Urmează descrierea castelului. Pe fiecare dintre următoarele MM linii se află câte NN numere naturale cuprinse între 11 şi MNM \cdot N reprezentând cheile necesare deschiderii fiecăreia dintre camere.

Date de ieșire

Fişierul de ieşire castel.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de camere accesibile prinţesei.

Restricții și precizări

  • 1M,N1501 \leq M, N \leq 150;
  • 1KMN1 \leq K \leq M \cdot N;
  • Odată ce prinţesa a păşit într-o cameră, respectiva cameră va rămâne pentru totdeauna deschisă.

Exemplu

castel.in

4 3 1
1 1 4
1 6 2
6 9 8
12 10 11

castel.out

7

Explicație

Prinţesa porneşte din camera 11. Aici foloseşe cheia 11 şi intră în camera 44. Se întoarce în camera 11 şi descuie camera 22. Foloseşte cheia luată din camera 44 şi descuie camera 33. În acest moment ea deţine cheile 11, 22, 33 şi 44. Foloseşte cheia 22 şi intră în camera 66, apoi foloseşte cheia 66 şi intră în camera 55, apoi în camera 44, de unde, folosind cheia luată din camera 66 intră în camera 77. La final prinţesa are cheile 11, 22, 33, 44, 55, 66, 77 şi nu mai poate deschide nici o altă cameră.

Log in or sign up to be able to send submissions!