distractie

Distractie

* 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. Restrictii si precizari

h3. Explicaţie

Un scenariu posibil este urmatorul: Adrian pleaca din casuta (1, 1) si merge pana in casuta (1, 3), unde va aplica prima vraja: 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 schimba culoarea casutei adiacente (3, 4) din 3 in 2, pentru a putea ajunge la finalul drumului.

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") ==