Cod sursa(job #605509)

Utilizator predator5047Butiu Alexandru Octavian predator5047 Data 29 iulie 2011 19:51:19
Problema Submultimi Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.14 kb
#include <fstream>
#include <iostream>
using namespace std;

short int a[101][101],n,m,v[4];
int lgpod=999999;
void citire(); void flood(int i,int j,int col,int tar);
void rgb(); void pod();
void lee(int i,int j); void afisare();
int main()
{
    citire();
    rgb();
    pod();

    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==-1)
            cout<<"R ";
            else if(a[i][j]==-2)
            {
                cout<<"G ";
            }
            else if(a[i][j]==-3)
            {
                cout<<"B ";
            }
            else
            cout<<a[i][j]<<" ";
        }
        cout<<"\n";
    }
    */
    afisare();
    return 0;
}

void pod()
{
    const int dx[]={1,0,-1,0};
    const int dy[]={0,1,0,-1};

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==0)
            {
                for(int k=0;k<4;k++)
                {
                    if(a[i][j]==0)
                    {
                        for(int k=0;k<4;k++)
                        {
                            int x=i+dx[k],y=j+dy[k];
                            if(a[x][y]*-1==2&&x>=1&&y>=1&&x<=n&&y<=m)
                            lee(i,j);
                        }
                    }
                }
            }
        }
    }
}

void lee(int i,int j)
{
    const int dx[]={1,0,-1,0};
    const int dy[]={0,1,0,-1};

    struct Coada
    {
        short int x;
        short int y;
    }q[10201];

    int StC=0,SfC=1;
    a[i][j]=1;
    q[1].x=i;
    q[1].y=j;
    while(StC<=SfC)
    {
        StC++;
        for(int k=0;k<4;k++)
        {
            int x2=q[StC].x+dx[k],y2=q[StC].y+dy[k];

            if(a[x2][y2]==0 &&x2>=1&&y2>=1&&x2<=n&&y2<=m)
            {
                a[x2][y2]=a[q[StC].x][q[StC].y]+1;
                SfC++;
                q[SfC].x=x2;
                q[SfC].y=y2;
            }
            else if(a[x2][y2]*-1==1&&x2>=1&&y2>=1&&x2<=n&&y2<=m)
            {
                if(lgpod>a[q[StC].x][q[StC].y])
                {
                    lgpod=a[q[StC].x][q[StC].y];
                }
            }
        }
    }
}




void rgb()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==1||a[i][j]==2||a[i][j]==3)
            {
                v[a[i][j]]++;
                flood(i,j,a[i][j]*-1,a[i][j]);
            }
        }
    }
}

void flood(int i,int j,int col,int tar)
{
    if(a[i][j]==tar&&i>=1&&j>=1&&i<=n&&j<=m)
    {
        a[i][j]=col;
        flood(i+1,j,col,tar);
        flood(i-1,j,col,tar);
        flood(i,j+1,col,tar);
        flood(i,j-1,col,tar);
    }
}

void afisare()
{
    ofstream fout("insule.out");

    fout<<v[1]<<" "<<v[2]<<" "<<v[3]<<" "<<lgpod;

    fout.close();
}

void citire()
{
    ifstream fin("insule.in");

    fin>>n>>m;
    char c;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            fin>>c;   //49=1,48=0,51=3,50=2,
            if(c==49)
            a[i][j]=1;
            else if(c==48)
            a[i][j]=0;
            else if(c==50)
            a[i][j]=2;
            else
            a[i][j]=3;
        }
    }
    fin.close();
}