Fişierul intrare/ieşire:distractie.in, distractie.outSursăACM ICPC Faza Nationala 2015
AutorDin FolclorAdăugată deneapuiuComisie ICPC UPB neapuiu
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.indistractie.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?