Cod sursa(job #1748959)

Utilizator FredyLup Lucia Fredy Data 27 august 2016 15:57:33
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.27 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define lim 401
char ini[lim][lim];
int P[lim*lim],NR[lim*lim],lnew,cnew,knou;
int n,m,rez;
int rezx,rezy;
char rezc;
int DL[4]={-1,0,1,0};
int DC[4]={0,1,0,-1};


int code(int x, int y)
{
    return x*m+y;
}



int p(int a)
{
    if (P[a]==a)
        return a;
    return p(P[a]);
}



void reuniune(int a, int b)
{
    int rada,radb,varfuri=0;
    rada=p(a);
    radb=p(b);

    if (rada!=radb)
    {
        if (NR[rada]<=NR[radb])
        {
            NR[radb]+=NR[rada];
            P[rada]=radb;
            varfuri=NR[radb];
        }
        else
        {
            NR[rada]+=NR[radb];
            P[radb]=rada;
            varfuri=NR[rada];
        }
        if (varfuri>rez)
            rez=varfuri;
    }
}





int main()
{
    int tip,i,j,pos,l,c,d,lnou,cnou;

    fin>>tip>>n>>m;

    for(i=0; i<n; i++)
        fin>>ini[i];

    for(i=0; i<=n*m; i++)
        P[i]=i, NR[i]=1;

    ///gasesc parintele fiecarei celule
    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
        {
            pos=code(i,j);
            l=i;
            c=j;
            for (d=0;d<=3;d++)
                {
                    lnou=l+DL[d];
                    cnou=c+DC[d];
                    if (lnou>=0 && lnou<n && cnou>=0 && cnou<m)
                        if(ini[l][c]==ini[lnou][cnou])
                        {
                            knou=code(lnou,cnou);
                            reuniune(pos,knou);
                        }
                }
        }

    ///prima cerinta
    if(tip==1)
        fout<<rez<<'\n';


    ///a doua cerinta
    if(tip==2)
    {
        rez=-1;
        int aux1,aux2,lnounou,cnounou,rada,radb,a,b;
        lnou=cnou=0;
        ///verific pt fiecare celula in ce culoare as putea sa o schimb
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
            {
                for(aux1=0; aux1<=3; aux1++)
                {
                    lnou=i+DL[aux1];
                    cnou=j+DC[aux1];
                    if (lnou>=0 && lnou<n && cnou>=0 && cnou<m)
                        for(aux2=0; aux2<=3; aux2++)
                        {
                            lnounou=i+DL[aux2];
                            cnounou=j+DC[aux2];

                            ///daca nu am iesit din matrice
                            ///daca nu e acelasi element
                            ///daca culorile sunt egale
                            if (lnounou>=0 && lnounou<n && cnounou>=0 && cnounou<m)
                                if(code(lnou,cnou)!=code(lnounou,cnounou))
                                    if(ini[lnou][cnou]==ini[lnounou][cnounou])
                                    {
                                        a=code(lnou,cnou);
                                        b=code(lnounou,cnounou);
                                        rada=p(a);
                                        radb=p(b);
                                        if(rada!=radb)
                                            if(NR[rada]+NR[radb]+1>rez)
                                            {
                                                rez=NR[rada]+NR[radb]+1;
                                                rezx=i;
                                                rezy=j;
                                                rezc=ini[lnounou][cnounou];
                                            }
                                        if(rada==radb && ini[i][j]!=ini[lnounou][cnounou])
                                            if(NR[rada]+1>rez)
                                            {
                                                rez=NR[rada]+1;
                                                rezx=i;
                                                rezy=j;
                                                rezc=ini[lnounou][cnounou];
                                            }
                                    }

                        }
                }
            }


        ///afisare
        fout<<rezx+1<<' '<<rezy+1<<'\n';
        fout<<rezc;

    }





    fin.close();
    fout.close();
    return 0;
}