Cod sursa(job #2451621)

Utilizator butnaru_vlad2003Butnaru Vlad butnaru_vlad2003 Data 27 august 2019 14:23:56
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda repost Marime 2.77 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream in ("insule.in");
ofstream out ("insule.out");
int a[102][102],nr1;
const int dirx[4]= {-1,0,1,0};
const int diry[4]= {0,-1,0,1};
struct info
{
    int x,y,val;
};
queue <info> coada;
int n,m;
bool verf (int caut1, int x2, int y2)
{
    if (x2<1 || x2>n || y2<1 || y2>m )
        return 0;
    if (a[x2][y2]!=caut1)
        return 0;
    else
        return 1;
}
bool verf2 (int x2, int y2)
{
    if (x2>=1 && x2<=n && y2>=1 && y2<=m)
    {
        if (a[x2][y2]==4)
            return 1;
        else
            return 0;
    }
    else
        return 0;
}
bool verf3 (int x2,int y2)
{
    if (x2>=1 && x2<=n && y2>=1 && y2<=m)
        return 1;
    else
        return 0;
}
void phill (int caut, int x1, int y1)
{
    if (verf(caut,x1,y1))
    {
        a[x1][y1]=caut+3;
        phill(caut,x1+1,y1);
        phill(caut,x1,y1+1);
        phill(caut,x1-1,y1);
        phill(caut,x1,y1-1);
    }
}
int lee ()
{
    info b;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
        {
            if (a[i][j]==0)
            {
                for (int k=0; k<=3; ++k)
                {
                    int i1=i+dirx[k],j1=j+diry[k];
                    if (verf2(i1,j1))
                    {
                        b.val=1;
                        b.x=i;
                        b.y=j;
                        coada.push(b);
                        a[i][j]=200;
                        break;
                    }
                }
            }
        }
    while (!coada.empty())
    {
        int i1=coada.front().x,j1=coada.front().y,distanta=coada.front().val;
        for (int k=0; k<=3; ++k)
        {
            int i2=i1+dirx[k],j2=j1+diry[k];
            if (verf3(i2,j2))
            {
                if (a[i2][j2]==5)
                    return distanta;
                else if (a[i2][j2]==0)
                {
                    b.val=distanta+1;
                    b.x=i2;
                    b.y=j2;
                    coada.push(b);
                    a[i2][j2]=200;
                }
            }
        }
        coada.pop();
    }
}
int main ()
{
    char nr;
    in>>n>>m;
    int nr1,nr2,nr3;
    nr1=nr2=nr3=0;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
        {
            in>>nr;
            a[i][j]=nr-'0';
        }
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=m; ++j)
        {
            if (a[i][j]==1)
            {
                nr1++;
                phill(1,i,j);
            }
            if (a[i][j]==2)
            {
                nr2++;
                phill(2,i,j);
            }
            if (a[i][j]==3)
            {
                nr3++;
                phill(3,i,j);
            }
        }
    out<<nr1<<' '<<nr2<<' '<<nr3<<' ';
    out<<lee();
    return 0;
}