== include(page="template/taskheader" task_id="padure") ==
Poveste si cerinta...
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.
h2. 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.
h2. 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.
h2. 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$
h2. Exemplu
table(example). |_. padure.in |_. padure.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. 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$
== include(page="template/taskfooter" task_id="padure") ==
