Fişierul intrare/ieşire:gradinarit2.in, gradinarit2.outSursăAdobe - Code Pandas
AutorTraian RebedeaAdăugată deadoberomaniaAdobe Romania adoberomania
Timp execuţie pe test2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gradinarit 2

Gigel, tanarul fermier din etapa anterioara, are aceeasi gradina de legume, dar a reusit sa isi diversifice activitatea si cultiva in acest moment mai multe tipuri de legume codificate prin litere de la 'A' la 'Z'.
Daca nu va pricepeti la cultivarea legumelor si ati uitat enuntul din etapa anterioara, lucrurile stau in felul urmator:

  • loturile sunt in general dreptunghiulare.
  • distanta intre randuri este egala, deci pe un lot dreptunghiular incap maxim N randuri, indiferent de tipul rasadurilor de pe fiecare rand.
  • pe fiecare rand, distanta intre doua rasaduri adiacente este egala, deci pe un rand incap maxim M rasaduri de legume, indiferent de tipul lor.

Din nou Gigel are toate rasadurile invadate de catre daunatori, iar tratamentele sunt in continuare diferite in functie de tipul de rasad, dar au acelasi pret indiferent de tipul lor.
Totusi, de data aceasta tratamentele au mai evoluat si omoara daunatorii pentru rasadul corespunzator doar daca este ultimul tratament aplicat pentru acel rasad particular (adica tratamentul pentru rosii omoara daunatorii de rosii atata timp cat nu s-a aplicat alt tratament mai tarziu). Mai mult, un tratament de un anumit tip nu omoara nici daunatorii si nici recolta din rasadurile de tipuri diferite.
O doza de tratament poate fi folosita pentru oricat de multe rasaduri consecutive de pe acelasi rand, dar nu se poate face pauza de folosire nici pentru a trece de la un rand la altul, nici pentru a trata rasaduri neconsecutive de pe acelasi rand deoarece timpul de nefolosire al tratamentului este prea mare, iar acesta se strica repede daca nu este folosit in continuu.

Cum dozele de tratament sunt scumpe, Gigel vrea sa afle care este numarul minim de doze de tratament pe care trebuie sa le cumpere pentru a salva toate rasadurile din gradina sa in conditiile specificate de problema.

Date de intrare

Fisierul de intrare gradinarit2.in contine:

* pe primul rand doua numere intregi: N - numarul de randuri, M - numarul de rasaduri de pe fiecare rand.
* pe urmatoarele N randuri sunt cate M numere care reprezinta ordinea rasadurilor de pe randul respectiv codificate printr-un sir de caractere de la 'A' la 'Z' separate prin cate un spatiu.

Date de iesire

In fisierul de iesire gradinarit2.out scrieti o singura linie ce contine un intreg care reprezinta numarul minim de doze de tratament cumparate pentru a salva toate rasadurile din gradina.

Restricţii

  • 0 ≤ N, M ≤ 60
  • Tipurile de rasad sunt codificate de la 'A' la 'Z'

Exemplu

gradinarit2.ingradinarit2.out
2 10
A B B C C B B A A A
A B B A A C C A D A
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?