# PBinfo #1028 – Ferma – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 ş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 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 ≤ 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
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

## Cod sursă C++

```cpp
//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);}
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1028)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1028/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1028/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)