== include(page="template/taskheader" task_id="ferma3") ==
Un fermier deţine o fermă de formă dreptunghiulară cu lungimea m metri şi lăţimea n metri. Respectând principiul rotaţiei culturilor, fermierul şi‑a realizat un plan pentru semănarea culturilor în noul an. Astfel ,el a desenat un dreptunghi pe care l-a împărţit în m * n celule, fiecare corespunzând unui metru pătrat, şi a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparţin aceleiaşi parcele dacă au aceeaşi culoare (sunt însămânţate cu aceeaşi cultură). Fermierul are posibilitatea să irige o sigură parcelă şi doreşte să aleagă parcela cu cea mai mare suprafaţă. Nefiind mulţumit de suprafaţa rezultată, s-a întrebat dacă ar putea schimba cultura de pe o singură celulă, astfel încât să obţină o parcelă de suprafaţă mai mare.
Un fermier deţine o fermă de formă dreptunghiulară cu lungimea m metri şi lăţimea $n$ metri. Respectând principiul rotaţiei culturilor, fermierul şi‑a realizat un plan pentru semănarea culturilor în noul an. Astfel ,el a desenat un dreptunghi pe care l-a împărţit în $m * n$ celule, fiecare corespunzând unui metru pătrat, şi a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparţin aceleiaşi parcele dacă au aceeaşi culoare (sunt însămânţate cu aceeaşi cultură). Fermierul are posibilitatea să irige o sigură parcelă şi doreşte să aleagă parcela cu cea mai mare suprafaţă. Nefiind mulţumit de suprafaţa rezultată, s-a întrebat dacă ar putea schimba cultura de pe o singură celulă, astfel încât să obţină o parcelă de suprafaţă mai mare.
!problema/ferma3?f1.jpg!
h2. Cerinta
Dându-se dimensiunile fermei şi pentru fiecare celulă culoarea corespunzătoare culturii semănate, determinaţi:
Varianta 1: Suprafaţa maximă a unei parcele în planul iniţial.
Varianta 2: Numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură şi culoarea corespunzătoare noii culturi în vederea obţinerii celei mai mari parcele posibile.
Varianta $1$: Suprafaţa maximă a unei parcele în planul iniţial.
Varianta $2$: Numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură şi culoarea corespunzătoare noii culturi în vederea obţinerii celei mai mari parcele posibile.
h2. Date de intrare
Fişierul de intrare $ferma3.in$ va conţine:
pe prima linie un număr natural v ( 1 ≤ v ≤ 2 ) indicând varianta cerinţei de rezolvare;
pe a doua linie două numere naturale m şi n separate printr-un spaţiu, cu semnificaţia din enunţ;
pe fiecare dintre următoarele m linii se găsesc câte n caractere (litere mici), reprezentând codurile culturilor ce vor fi semănate pe cele n celule corespunzătoare fiecărei linii.
Fişierul de intrare $ferma3.in$ va conţine: Pe prima linie un număr natural $v$ $(1 ≤ v ≤ 2)$ indicând varianta cerinţei de rezolvare. Pe a doua linie două numere naturale $m$ şi $n$ separate printr-un spaţiu, cu semnificaţia din enunţ. Pe fiecare dintre următoarele $m$ linii se găsesc câte $n$ caractere (litere mici), reprezentând codurile culturilor ce vor fi semănate pe cele n celule corespunzătoare fiecărei linii.
h2. Date de ieşire
Fişierul de ieşire $ferma.out$ va conţine:
Varianta 1 – pentru v=1:
pe prima linie numărul natural s, reprezentând suprafaţa maximă a unei parcele.
Varianta 2 – pentru v=2:
pe prima linie două numere naturale separate printr-un spaţiu, reprezentând numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură, în vederea obţinerii unei parcele cu suprafaţa maximă;
Varianta $1$ – pentru $v=1$: pe prima linie numărul natural $s$, reprezentând suprafaţa maximă a unei parcele.
Varianta $2$ – pentru $v=2$: pe prima linie două numere naturale separate printr-un spaţiu, reprezentând numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură, în vederea obţinerii unei parcele cu suprafaţa maximă;
pe a doua linie un caracter reprezentând codul culorii corespunzătoare noii culturi din celula determinată.
h2. Restricţii
* $2 ≤ m ≤ 400$
* $2 ≤ n ≤ 400$
* $Numărul de culturi distincte este cel puţin 2 şi cel mult 26.$
* $30% din teste vor avea pe prima linie valoarea 1, iar restul de 70% din teste vor avea pe prima linie valoarea 2.$
* $Pentru varianta 2 se punctează orice soluţie care conduce la obţinerea unei parcele cu suprafaţa maximă. Nu se acordă punctaje parţiale.$
* Numărul de culturi distincte este cel puţin $2$ şi cel mult $26$.
* $30%$ din teste vor avea pe prima linie valoarea $1$, iar restul de $70%$ din teste vor avea pe prima linie valoarea $2$.
* Pentru varianta $2$ se punctează orice soluţie care conduce la obţinerea unei parcele cu suprafaţa maximă. Nu se acordă punctaje parţiale.
h2. Exemplu
h3. Explicaţie
Datele corespund imaginilor de mai sus. Numerotarea parcelelor din imaginea 2 este utilizată pentru a simplifica explicaţiile de mai jos şi nu influenţează datele problemei şi nici algoritmul de rezolvare.În varianta 1 se determină şi se afişează suprafaţa maximă a unei parcele, care este egală cu 11 şi corespunde parcelei 6, de culoare verde (codificată cu litera v în imaginea 1 şi în fişierul de intrare).
!problema/ferma3?f2.jpg!
Datele corespund imaginilor de mai sus. Numerotarea parcelelor din imaginea $2$ este utilizată pentru a simplifica explicaţiile de mai jos şi nu influenţează datele problemei şi nici algoritmul de rezolvare.În varianta $1$ se determină şi se afişează suprafaţa maximă a unei parcele, care este egală cu $11$ şi corespunde parcelei $6$, de culoare verde (codificată cu litera $v$ în imaginea $1$ şi în fişierul de intrare).
== include(page="template/taskfooter" task_id="ferma3") ==
