Arhipelagul RGB este format din insule care aparţin ţărilor R, G şi B. Putem reprezenta harta arhipelagului ca o matrice cu n linii şi m coloane cu elemente din mulţimea {0, 1, 2, 3}. Un element egal cu 0 reprezintă o zonă acoperită de apă; un element egal cu 1 reprezintă o zonă de pământ aparţinând unei insule din ţara R, iar un element egal cu 2 reprezintă o zonă de pământ aparţinând unei insule din ţara G, iar un element egal cu 3 reprezintă o zonă de pământ aparţinând unei insule din ţara B.

Se consideră că două elemente ale matricei sunt vecine dacă ele au aceeaşi valoare şi fie sunt consecutive pe linie, fie sunt consecutive pe coloană. Două elemente aparţin aceleiaşi insule dacă ele sunt vecine sau dacă se poate ajunge de la un element la celălalt pe un drum de-a lungul căruia oricare două elemente consecutive sunt vecine.

Pentru a încuraja relaţiile de colaborare dintre ţările R şi G, se doreşte construirea unui pod care să unească o insulă aparţinând ţării R de o insulă aparţinând ţării G. Podul trebuie să respecte următoarele condiţii:

să înceapă pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparţinând ţării R;
să se termine pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparţinând ţării G;
să traverseze numai zone acoperite cu apă;
oricare două elemente consecutive ale podului trebuie să fie vecine;
lungimea podului să fie minimă (lungimea podului este egală cu numărul de elemente traversate de pod).

Cerinţă

Dată fiind harta arhipelagului să se determine câte insule aparţin fiecărei ţări, precum şi lungimea minimă a unui pod care să satisfacă condiţiile din enunț.

Date de intrare

Fişierul de intrare insule.in conţine pe prima linie numerele naturale n şi m, separate prin spaţiu. Pe următoarele n linii este descrisă harta arhipelagului. Pe fiecare dintre aceste n linii sunt scrise câte m valori din mulţimea {0, 1, 2, 3}; valorile nu sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire insule.out va conţine o singură linie pe care vor fi scrise patru numere naturale separate prin spaţii NR NG NB Lg, unde NR reprezintă numărul de insule aparţinând ţării R, NG numărul de insule aparţinând ţării G, NB numărul de insule aparţinând ţării B, iar Lg lungimea minimă a podului.

Restricţii şi precizări

1 < n, m ≤ 100
Se garantează că pe hartă există cel puţin un element 1, un element 2 şi un element 0.
Se acordă 40% din punctaj pentru determinarea corectă a numărului de insule din fiecare ţară; se acordă punctaj integral pentru rezolvarea corectă a tuturor cerinţelor.
Începutul şi sfârşitul podului pot să coincidă.
Pentru datele de test există întotdeauna soluţie.

Exemplu

insule.in

insule.out

4 2 3 4

Explicație

Ţara R are 4 insule, ţara G are 2 insule, iar ţara B are 3 insule.

Lungimea minimă a unui pod care poate fi construit este 4; de exemplu, podul traversează celulele (6,5), (6,4), (6,3), (6,2).

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

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("insule.in");
ofstream fout("insule.out");
int di[]={0,0,1,-1}, dj[]={1,-1,0,0}, a[101][101],n,m;
int R[4];
 
void citire(){
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;++j){
            char c;
            fin>>c;
            a[i][j] = c-'0';
        }
}
 
void fill(int i,int j,int vc, int vn){
    if(i>0 && j>0 && i<=n && j<=m && a[i][j]==vc){
        a[i][j]=vn;
        for(int k=0;k<4;++k)
            fill(i+di[k], j+dj[k],vc,vn);
    }
}
 
int Vecin(int i,int j,int v){
    //verifica daca poz )i,j) are un vecin egal cu v
    for(int k=0;k<4;++k)
        if(a[i+di[k]][j+dj[k]]==v)
            return 1;
    return 0;
}
 
void lee(){
    int st,dr,L[10001],C[10001];
    st=1,dr=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(a[i][j]==0 && Vecin(i,j,-1)){
                a[i][j]=1;
                dr++;L[dr]=i, C[dr]=j;
            }
    while(st<=dr){
        int i=L[st],j=C[st];
        for(int k=0;k<4;++k){
            int ii = i+di[k],jj=j+dj[k];
            if(ii>0 && ii<=n && jj>0 && jj<=m && a[ii][jj]==0){
                a[ii][jj]=a[i][j]+1;
                dr++; L[dr]=ii , C[dr]=jj;
                if(Vecin(ii,jj,-2)){
                    fout<<" "<<a[ii][jj]<<endl;
                    exit(0);
                }
            }
        }
        st++;
    }
}
 
int main(){
    citire();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(a[i][j]>0){
                R[a[i][j]]++;
                fill(i,j,a[i][j],-a[i][j]);
            }
    fout<<R[1]<<" "<<R[2]<<" "<<R[3];
    lee();
    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 #1099 Insule

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