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.
Cerinţă
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.
Date de intrare
Fişierul de intrare
ferma1.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.
Date de ieşire
Fişierul de ieşire
ferma1.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ă;
• pe a doua linie un caracter reprezentând codul culorii corespunzătoare noii culturi din celula determinată.
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.
Exemple
ferma1.in | ferma1.out | Explicaţii |
1
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag
| 11
|
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).
|
2
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag
| 20
3 4
v
| Pentru varianta 2:
Schimbând în verde (v) culoarea celulei de pe linia 3 şi coloana 4, se obţine o parcelă cu suprafaţa 11+8+1=20 (se unesc parcelele cu numărul 6 respectiv 8).
O altă soluţie corectă este:
4 4
v
|