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:
- Cerința 1: Suprafața maximă a unei parcele în planul inițial.
- Cerința 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 ferma.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şinseparate printr-un spațiu, cu semnificația din enunț; - pe fiecare dintre următoarele
mlinii se găsesc câtencaractere (litere mici), reprezentând codurile culturilor ce vor fi semănate pe celencelule corespunzătoare fiecărei linii.
Date de ieşire
Fișierul de ieșire ferma.out va conține:
Cerința 1 – pentru v=1:
- pe prima linie numărul natural s, reprezentând suprafața maximă a unei parcele.
Cerința 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 şi precizări
2 ≤ m ≤ 4002 ≤ n ≤ 400- Numărul de culturi distincte este cel puţin
2şi cel mult26. 30%din teste vor avea pe prima linie valoarea1, iar restul de70%din teste vor avea pe prima linie valoarea2.- Pentru varianta
2se punctează orice soluție care conduce la obținerea unei parcele cu suprafața maximă. Nu se acordă punctaje parțiale.
Exemple
ferma.in
1 7 8 rmmgggaa mvvgggaa mvvgvvvv vvvrvvvv vvrrrgga vvrrrggg aaaaaaag
ferma.out
11
ferma.in
2 7 8 rmmgggaa mvvgggaa mvvgvvvv vvvrvvvv vvrrrgga vvrrrggg aaaaaaag
ferma.out
3 4 v
Explicație
Pentru primul exemplu:
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).
Pentru al doilea exemplu:
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
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Ferma:
//Prof Nicu Vlad-Laurentiu - Liceul Teoretic "Mihail Kogalniceanu" Vaslui
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=405;
int n, m, nrzones;
char a[N][N],cu;
int b[N][N], dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1}, d[N*N],p;
bool c[N*N];
void filll(int x, int y)
{
b[x][y]=nrzones;
d[nrzones]++;
for(int i=0;i<4;i++)
{
if(!b[x+dx[i]][y+dy[i]]&&a[x][y]==a[x+dx[i]][y+dy[i]]) filll(x+dx[i], y+dy[i]);
}
}
int main()
{
freopen("ferma.in", "r", stdin);
freopen("ferma.out", "w", stdout);
int i, j, k, l, sol=0, s=0,v,ma=0,p=0;
pair<int, int> soli;
scanf("%d\n%d%d",&v, &n, &m);
for(i=1;i<=n;i++)
{
scanf("%s", a[i]+1);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(!b[i][j])
{
nrzones++;
filll(i, j);
if(ma<d[nrzones]){ma=d[nrzones];}
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
char aux=a[i][j];
for(k=0;k<4;k++)
{
a[i][j]=a[i+dx[k]][j+dy[k]];
for(l=0, s=0;l<4;l++)
{
if(!c[b[i+dx[l]][j+dy[l]]]&&a[i][j]==a[i+dx[l]][j+dy[l]])
{
c[b[i+dx[l]][j+dy[l]]]=1;
s+=d[b[i+dx[l]][j+dy[l]]];
}
}
if(!c[b[i][j]]) s++;
if(s>sol)
{
sol=s; cu=a[i][j];
soli=make_pair(i, j);
}
for(l=0;l<4;l++)
{
c[b[i+dx[l]][j+dy[l]]]=0;
}
}
a[i][j]=aux;
}
}
if(v==1) printf("%d\n",ma);
else{printf("%d %d\n", soli.first, soli.second);
printf("%c\n",cu);}
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1028 Ferma
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1028 Ferma de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!