northcoders_insule.cpp

#include <fstream>
#include <cstring>
#include <algorithm>
#define MAXN 510
#define MAXM 1000000
#define MAXI 25000
using namespace std;
string s;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int n,m,a[MAXN][MAXN],insula[MAXN][MAXN],p,k,t[MAXI];
short int X[MAXM],Ind[MAXM],Y[MAXM],Cost[MAXM];
int grupa(int x)
{
    if(t[x]==x) return x;
    t[x]=grupa(t[x]);
    return t[x];
}
void reunite(int x,int y)
{
    int key=grupa(x);
    t[key]=grupa(y);
}
bool cmp(int x,int y)
{
    return Cost[x]<Cost[y];
}
void df(int x,int y)
{
    int i,j;
    insula[x][y]=k;
    for(int d=0;d<4;d++)
    {
        i=dx[d]+x; j=dy[d]+y;
        if(a[i][j] and !insula[i][j]) df(i,j);
    }
}
int main()
{
    int last,pod,nr,i,j;
    ifstream fi("insule.in");
    ofstream fo("insule.out");
    fi>>n>>m;
    getline(fi,s);
    for(i=1;i<=n;i++)
    {
        getline(fi,s);
        for(j=0;j<m;j++)
        a[i][j+1]=s[j]-'0';
    }
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    if(a[i][j] and !insula[i][j])
    {
        k++;
        df(i,j);
    }
    //unesc pe linie
    for(i=1,p=0;i<=n;i++)
    {
        last=0;
        for(j=1;j<=m;j++)
        if(a[i][j])
        {
            if(last and insula[i][last]!=insula[i][j])
            {
                X[++p]=insula[i][last];
                Y[p]=insula[i][j];
                Cost[p]=j-last-1;
                Ind[p]=p;
            }
            last=j;
        }
    }
    //unesc pe coloana
    for(j=1;j<=m;j++)
    {
        last=0;
        for(i=1;i<=n;i++)
        if(a[i][j])
        {
            if(last and insula[last][j]!=insula[i][j])
            {
                X[++p]=insula[last][j];
                Y[p]=insula[i][j];
                Cost[p]=i-last-1;
                Ind[p]=p;
            }
            last=i;
        }
    }
    sort(Ind+1,Ind+p+1,cmp);
    //Kruskal
    for(i=1;i<=k;i++) t[i]=i;
    for(i=1,nr=0,pod=0;i<=p and nr!=k-1;i++)
    if(grupa(X[Ind[i]])!=grupa(Y[Ind[i]]))
    {
        reunite(X[Ind[i]],Y[Ind[i]]);
        pod+=Cost[Ind[i]];
        nr++;
    }
    fo<<pod<<"\n";
    return 0;
}