Într-un oraş se află o grădină de formă dreptunghiulară, formată din n x m pătrăţele, aranjate sub forma unei matrice cu n linii şi m coloane. Într-un pătrăţel poate fi cultivată o singură plantă, de o anumită specie. Speciile sunt identificate prin numere distincte cuprinse între 1 şi s. Datorită fenomenelor meteorologice, în unele pătrăţele nu mai există flori.

Solul fiecărui pătrăţel are un anumit coeficient de umiditate. Pentru cultivare, fiecare specie de flori are nevoie de o valoare minimă a umidităţii solului. Mai exact, dacă umiditatea solului dintr-un pătrăţel este mai mică decât umiditatea specifică plantei, aceasta nu poate fi cultivată în pătrăţelul respectiv. Proprietarul grădinii doreşte să o reamenajeze, prin păstrarea plantelor deja existente, dar şi prin cultivarea de noi plante în pătrăţelele din care florile au dispărut, astfel încât să se obţină o zonă de arie cât mai mare acoperită cu plante din aceeaşi specie.

Se numeşte zonă un grup de pătrăţele, astfel încât oricare două pătrăţele din zonă fie sunt învecinate (adică au o latură comună), fie se poate ajunge de la unul la celălalt, deplasându-ne numai de la un pătrăţel la unul învecinat cu el. Aria unei zone este egală cu numărul de pătrăţele din care este formată zona.

Cerința

Determinaţi valoarea ariei pentru zona de arie maximă cultivată cu plante din aceeaşi specie, obţinută în urma reamenajării grădinii.

Date de intrare

Fișierul de intrare gradina1.in conţine pe prima linie trei numere naturale nenule separate prin câte un spaţiu n, m şi s unde n, m reprezintă numărul de linii, respectiv numărul de coloane ale matricei ce reprezintă grădina, iar s este numărul de specii de plante ce pot fi cultivate în grădină.

Pe următoarele n linii se află câte m numere naturale cuprinse între 0 şi s, reprezentând matricea T, ce codifică grădina astfel: al j-lea element de pe linia i+1 a fişierului (T[i][j]) este egal cu 0, dacă pătrăţelul respectiv nu conţine flori sau, în caz contrar, este egal cu numărul speciei florii.

Pe linia n+2 se află s numere naturale, separate prin câte un spaţiu, ce reprezintă în ordine coeficienţii de umiditate minimă necesari pentru cele s specii de flori.

Pe următoarele n linii se află câte m numere naturale separate prin câte un spaţiu; al j-lea număr de pe cea de a (n+2+i)-a linie din fişier reprezintă coeficientul de umiditate a solului din pătrăţelul situat pe linia i şi coloana j a grădinii.

Date de ieșire

Fișierul de ieșire gradina1.out va conţine o singură linie pe care va fi scris un număr natural, reprezentând valoarea ariei pentru zona de arie maximă cultivată cu plante din aceeaşi specie, în urma reamenajării grădinii.

Restricții și precizări

4 ≤ n, m ≤ 50
2 ≤ s ≤ 100
Coeficienţii de umiditate ai speciilor şi a solului sunt numere naturale nenule mai mici decât 1000

Exemplu

gradina1.in

6 6 5
2 0 0 1 4 4
0 0 1 1 0 0
0 0 0 0 3 0
0 1 5 5 0 0
1 2 2 0 5 4
5 2 0 0 3 0
10 6 4 9 8
10 20 3 10 5 10
2 12 20 8 7 9
14 5 9 8 10 2
2 16 15 14 7 2
12 14 12 15 14 12
11 14 11 9 11 12

gradina1.out

Explicație

Valoarea afişată în fişierul de ieşire este aria pentru zona de arie maximă ocupată de specia 3 şi formata din 10 pătrăţele ce ocupă poziţiile: (1,2), (2,2), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (4,5)

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 gradina1:

#include <bits/stdc++.h>

using namespace std;

ifstream fin("gradina1.in");
ofstream fout("gradina1.out");

const int dl[]={-1,0,1,0};
const int dc[]={0,1,0,-1};

int n,m,s,a[60][60],b[60][60],u[101], amax, ac, k;

void Read()
{
    int i, j;
    fin >> n >> m >> s;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            fin >> a[i][j];
    for (i = 1; i <= s; i++)
        fin >> u[i];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            fin >> b[i][j];
    fin.close();
}

void Bordare()
{
    int i;
    for (i = 0; i <= m + 1; i++)
        a[0][i] = a[n + 1][i] = 200;
    for (i = 1; i <= n; i++)
        a[i][0] = a[i][m + 1] = 200;
}

void Fill(int l, int c)
{
    int i;
    for (i = 0; i < 4; i++)
        if (a[l+dl[i]][c+dc[i]]==k)
        {
            ac++;
            a[l+dl[i]][c+dc[i]]=200;
            Fill (l+dl[i],c+dc[i]);
        }
        else if (a[l+dl[i]][c+dc[i]]!=-k && a[l+dl[i]][c+dc[i]]<=0
                 && b[l+dl[i]][c+dc[i]]>=u[k])
        {
            ac++;
            a[l+dl[i]][c+dc[i]]=-k;
            Fill(l+dl[i],c+dc[i]);
        }
}

int main ()
{
    Read();
    Bordare();
    int l, c;
    for (l = 1; l <= n; l++)
        for (c = 1; c <= m; c++)
            if (a[l][c] >= 1 && a[l][c] <= s)
            {
                ac = 1;
                k = a[l][c];
                a[l][c] = 200;
                Fill(l, c);
                if (ac > amax) amax = ac;
            }
    fout << amax << "\n";
    fout.close();
    return 0;
}

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 Adresa de email .

Rezolvarea problemei #2227 gradina1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2227 gradina1 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!

Rezolvare completă PbInfo #2227 gradina1