Pe un teren de formă dreptunghiulară s-au semănat mai multe tipuri de plante. Despre fiecare metru pătrat al terenului se ştie cu ce fel de plantă a fost semănat. Terenul poate fi reprezentat ca o matrice dreptunghiulară de dimensiuni ( – numărul de linii şi numărul de coloane). În fiecare celulă a matricei este exact un tip de plantă.
Se numeşte tabelă de plantă o porţiune din teren de formă dreptunghiulară pe care s-a semănat un acelaşi tip de plantă.
Cerinţă
Să se scrie un program care determină numărul minim de tabele de plante în care se poate împărţi terenul dat.
Date de intrare
Fişierul de intrare ogorul.in
are pe prima linie două numere naturale şi despărţite printr-un spaţiu, reprezentând dimensiunile terenului, iar pe următoarele linii denumirile plantelor cu care s-a semănat fiecare metru pătrat. Matricea care reprezintă terenul se traversează linie după linie, iar pe linie de la stânga la dreapta.
Date de ieșire
Numărul minim de tabele se va scrie pe prima linie a fişierului de ieşire ogorul.out
.
Restricții și precizări
- Denumirea plantelor este un şir de caractere de lungime maximă .
Exemplul 1
ogorul.in
4 5
grau
grau
grau
cartof
cartof
grau
grau
grau
cartof
cartof
grau
grau
porumb
porumb
porumb
grau
grau
porumb
porumb
porumb
ogorul.out
4
Exemplul 2
ogorul.in
4 5
grau
grau
grau
porumb
porumb
grau
grau
grau
porumb
porumb
grau
grau
grau
cartofi
cartofi
grau
grau
cartofi
cartofi
cartofi
ogorul.out
5