Revizia anterioară Revizia următoare
| 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).
Date de intrare
Fişierul de intrare distractie.in ...
Date de ieşire
În fişierul de ieşire distractie.out ...
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 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.
