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