top of page

Insule

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} astfel:

  • 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

  • un element egal cu 2 reprezintă o zonă de pământ aparÅ£inând unei insule din Å£ara G

  • 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).

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 enunt.

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 si 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

Heading 1

Implementare

#include <iostream>

#include <fstream>

#define Max 999999999

using namespace std;

 

ifstream f ("insule.in");

ofstream g ("insule.out");

int k,m,n,i,j,nl,nc,a[105][105],in,sf,K,K1,K2;

char sir[100];

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

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

struct lee

{

    int l,c;

} c[100001],u;

int b[105][105];

void fill (int x,int y,int k)

{

    if(b[x][y] == k)

    {

        b[x][y] = -k;

        fill(x,y+1,k);

        fill(x+1,y,k);

        fill(x-1,y,k);

        fill(x,y-1,k);

    }

}

void bordare()

{

    for(i = 0; i <= n+1; i++)

        a[0][i] = a[n+1][i] = -1;

    for(i = 0; i <= m+1; i++)

        a[i][0] = a[i][m+1] = -1;

}

void cerinta1()

{

    for(i = 1; i <= n; i++)

        for(j = 1; j <= m; j++)

        {

            if(b[i][j] == 1)

            {

                K++;

                k = 1;

                fill(i,j,k);

            }

            else if(b[i][j] == 2)

            {

                K1++;

                k = 2;

                fill(i,j,k);

            }

            else if(b[i][j] == 3)

            {

                K2++;

                k = 3;

                fill(i,j,k);

            }

        }

    g<<K<<" "<<K1<<" "<<K2<<" ";

}

void cerinta2()

{

    while(in <= sf)

    {

        u=c[in];

        for(i = 0; i < 4; i++)

        {

            nl = u.l + dl[i];

            nc = u.c + dc[i];

            if((a[nl][nc] > a[u.l][u.c] + 1 && b[u.l][u.c] != -2)||(b[nl][nc] == -2 && a[u.l][u.c] + 1  > 2&&b[u.l][u.c] != -2))

            {

                a[nl][nc] = a[u.l][u.c] + 1;

                c[++sf].l = nl;

                c[sf].c = nc;

                if(b[nl][nc] == -2 && a[nl][nc] > 2)

            {

                in=sf+2;

                break;

            }

            }

        }

        in++;

    }

    g<<a[nl][nc]-2;

}

int main()

{

    f >> n >> m;

    for(i = 1; i <= n; i++)

    {

        f >> sir;

        for(j = 0; j < m; j++)

        {

            a[i][j+1] = b[i][j+1] = sir[j] - 48;

            if(a[i][j+1] == 1)

            {

                c[++sf].l = i;

                c[sf].c = j+1;

                a[i][j+1] = 1;

            }

            else

            if(a[i][j+1] == 3)

                a[i][j+1] = -1;

            else

                a[i][j+1] = Max;

        }

    }

    bordare();

    cerinta1();

    cerinta2();

    return 0;

}

bottom of page