Fişierul intrare/ieşire:padure.in, padure.outSursăStelele Informaticii 2006, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Padure

Daca va intrebati ce mai face printul Algorel, acum puteti afla. El se afla pierdut undeva prin Padurea Magica si cauta cu disperare drumul inapoi spre castelul sau. Padurea Magica poate fi reprezentata ca o matrice cu N linii si M coloane, pentru fiecare celula din padure stiindu-se tipul copacilor care o acopera (numar natural mai mic decat 104). O celula este acoperita numai cu copaci de acelasi tip. Printul Algorel se afla undeva in celula (pl, pc) (pl reprezinta linia, pc coloana) iar castelul se afla situat in celula (cl, cc). Printul Algorel se poate deplasa in cele patru directii: Nord, Sud, Est si Vest, dar nu poate sa iasa din padure fiindca dincolo de padure e taramul Spanului cel Rau. In drumul sau catre castel, el trebuie sa plateasca Padurarului Magician un diamant pentru fiecare trecere dintr-o celula in alta in care se schimba tipul copacilor (adica daca cele doua celule sunt acoperite cu tipuri diferite de copaci). Pentru trecerile intre celule acoperite de acelasi tip de copaci el nu plateste nimic. Cum diamantele sunt resursa cea mai importanta in regat, el vrea sa stie numarul minim de diamante pe care trebuie sa-l plateasca pentru a ajunge la castel.

Date de intrare

Prima linie a fisierului padure.in se afla 6 numere naturale N M pl pc cl cc, cu semnificatia de mai sus. Urmatoarele N linii contin cate M numere naturale separate prin spatii, reprezentand tipul copacilor care acopera fiecare celula din Padurea Magica.

Date de iesire

Fisierul de iesire padure.out trebuie sa contina pe prima linie un singur numar intreg D reprezentand numarul minim de diamante pe care Algorel este nevoit sa-l plateasca pentru a ajunge la castel.

Restrictii

  • 1 ≤ N, M ≤ 1000
  • 1 ≤ pl, cl ≤ N si 1 ≤ pc, cc ≤ M
  • Pozitia initiala a lui Algorel nu coincide cu cea a castelului
  • Pentru 50% din teste N, M ≤ 100

Exemplu

padure.inpadure.out
6 5 1 1 5 4
0 0 0 5 6
7 7 1 1 1
1 1 1 3 1
1 1 2 2 1
0 0 9 0 0
0 0 0 0 9
2

Explicatie

0 0 0 5 6
7 7 1 1 1
1 1 1 3 1
1 1 2 2 1
0 0 9 0 0
0 0 0 0 9

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content