Cod sursa(job #2341961)

Utilizator sergiudnyTritean Sergiu sergiudny Data 12 februarie 2019 13:58:40
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>
#define DM 1005
#define pb push_back
using namespace std;
ifstream fin("pirati.in");
ofstream fout("pirati.out");

int x1,x2,y1,y2,n,m,q,mt[DM][DM],nrIns,ins,ap;
int di[]={1,1,1,-1,-1,-1,0,0};
int dj[]={-1,0,1,-1,0,1,1,-1};
char c;
bitset<DM>isEarth[DM],viz[DM];
bitset<DM*3>added;
vector<int>G[3][DM]; /// 0 - ape 1 - insula 2 - final
bool isOk(int i,int j){ return i && j && i<=n && j<=m; }

void dfs(int i,int j,int cul, bool earth){
    mt[i][j]=cul;
    for(int d=0;d<8;++d){
        int ii = i+di[d];
        int jj = j+dj[d];
        if(isOk(ii,jj) && isEarth[ii][jj]==earth && !mt[ii][jj])
            dfs(ii,jj,cul,earth);
    }
}

void afis(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            fout<<mt[i][j]<<" ";
        fout<<'\n';
    }
}

void _search(int i,int j){
    viz[i][j]=1;
    bool type = isEarth[i][j];
    int val = mt[i][j];
    for(int d=0;d<8;++d){
        int ii = i+di[d];
        int jj = j+dj[d];
        int nxt = mt[ii][jj];
        if(isOk(ii,jj)){
            if(!added[val]) G[type][val].pb(nxt), added[val]=1;
            if(mt[ii][jj]==mt[i][j] && !viz[ii][jj]) _search(ii,jj);
        }
    }
}

int main()
{
    fin>>n>>m>>q;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
        fin>>c;
        isEarth[i][j]=c-'0';
    }
    fin>>x1>>y1>>x2>>y2;
    ///Set figures
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(!mt[i][j]){
        int index = isEarth[i][j]?++ins:++ap;
        dfs(i,j,index,isEarth[i][j]);
    }

    ///Set the tree
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(!viz[i][j]){
        viz[i][j]=1;
        _search(i,j);
    }

    for(int i=1;i<=ap;++i) for(auto j:G[0][i])
        for(auto toAdd:G[1][j])
            G[2][i].pb(toAdd);

    for(int i=1;i<=ap;++i){
        for(auto j:G[2][i])
            fout<<j<<" ";
        fout<<'\n';
    }

    return 0;
}