== include(page="template/taskheader" task_id="distractie") ==
Poveste şi cerinţă...
Adrian, copilul minune al informaticii, a descoperit in sfarsit comoara de noroc din spatele casei si a fost recompensat cu primul sau job: zugrav. Locul sau de munca are forma unei matrici cu *N* linii si *M* coloane, iar el initial se afla in casuta din stanga-sus *(1, 1)* si vrea sa ajunga in casuta din dreapta-jos *(N, M)*. Fiecare casuta din matrice are asociata o culoare, reprezentata de un numar natural cuprins intre *1* si *2000*. Adrian, in timpul calatoriei sale, trebuie sa satisfaca urmatoarele conditii:
* dintr-o casuta *(i, j)*, el se poate deplasa doar in casuta adiacenta de la dreapta *(i, j+1)* sau in casuta de jos *(i+1, j)* (nu poate depasi granitele matricei).
* casuta urmatoare in care se deplaseaza trebuie sa aiba aceeasi culoare ca casuta curenta.
A doua conditie nu poate fi indeplinita intotdeauna, insa Adrian are la dispozitie versuri profunde pe care daca le canta, camerele isi schimba culoarea. Astfel, atunci cand Adrian canta, la alegerea lui se intimpla unul dintre urmatoarele doua evenimente:
* culoarea casutei curente (in care se afla) se schimba intr-o culoare pe care o alege Adrian.
* culorea unei casute adiacente (stanga, dreapta, sus si jos) casutei in care se afla Adrian isi va schimba culoarea in una pe care el o alege.
Determinati *numarul minim* de cantece pe care Adrian trebuie sa le cante ca sa ajunga din casuta *(1, 1)* in casuta *(N, M)*, indeplinind toate conditiile impuse.
h2. Date de intrare
Fişierul de intrare $distractie.in$ ...
Fisierul de intrare $distractie.in$ contine pe prima linie, despartite prin cate un spatiu, doua numere naturale *N* si *M*, reprezentand numarul de linii, respectiv de coloane ale matricei. Pe urmatoarele *N* linii se afla cate *M* numere naturale cuprinse intre 1 si 2000, reprezentand culoarea fiecarei casute din matrice.
h2. Date de ieşire
În fişierul de ieşire $distractie.out$ ...
În fisierul de ieşire $distractie.out$ se va scrie pe prima linie un singur numar: numarul minim de cantece pe care Adrian trebuie sa le cante astfel incat sa poata ajunge la destinatie, indeplinind toate conditiile impuse lui.
h2. Restricţii
h2. Restrictii si precizari
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 800$
* $1 ≤ toate numerele din matrice ≤ 2000$
h2. Exemplu
table(example). |_. distractie.in |_. distractie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 4
1 1 1 2
4 5 6 2
6 7 4 3
| 2
|
h3. Explicaţie
...
Un scenariu posibil este urmatorul: Adrian pleaca din casuta (1, 1) si merge pana in casuta (1, 3), unde va canta un cantec si va schimba culoarea casutei curente din 1 in 2, pentru a se putea deplasa la dreapta. Continua drumul (pe ultima coloana) si ajunge pe pozitia (2, 4), unde va canta al doilea cantec si va schimba culoarea casutei adiacente (3, 4) din 3 in 2, pentru a putea ajunge la pasul urmator la finalul drumului.
== include(page="template/taskfooter" task_id="distractie") ==
== include(page="template/taskfooter" task_id="distractie") ==
