| Fişierul intrare/ieşire: | distractie.in, distractie.out | Sursă | ACM ICPC Faza Nationala 2015 |
| Autor | Din Folclor | Adăugată de |  Comisie ICPC UPB •neapuiu |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Distractie
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.
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.
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.
Restrictii si precizari
- 1 ≤ N, M ≤ 800
- 1 ≤ toate numerele din matrice ≤ 2000
Exemplu
| distractie.in | distractie.out |
|---|---|
| 3 4 1 1 1 2 4 5 6 2 6 7 4 3 | 2 |
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.
