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

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.

Fişierul de intrare $distractie.in$ ...

h2. Date de ieşire

Î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.

În fişierul de ieşire $distractie.out$ ...

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 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.

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.

== include(page="template/taskfooter" task_id="distractie") ==