Cod sursa(job #1845288)

Utilizator DobosDobos Paul Dobos Data 11 ianuarie 2017 09:57:57
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <deque>
#include <vector>
#define NMAX 105

const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};

using namespace std;

struct point {

    int x,y;

};


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

int M[NMAX][NMAX],V[NMAX];
deque < point > Q;
vector < int > A;
inline void Fill(int camera,int x,int y){

    int nx,ny;
    Q.push_back({x,y});
    M[x][y] = camera; V[camera] ++;
    while(!Q.empty()){
        x = Q.front().x;
        y = Q.front().y;
        Q.pop_front();
        for(int i = 0; i < 4; i++){
            nx = x + dx[i];
            ny = y + dy[i];
            if(M[nx][ny] == 0){
                M[nx][ny] = camera;
                V[camera] ++;
                Q.push_back({nx,ny});
            }
        }
    }
}

inline void cauta(int x, int y){
    int j,nx,ny;
    for(int i = 0; i < 4; i ++){
        nx = x + dx[i];
        ny = y + dy[i];
        if(M[nx][ny] != -1){
            for(j = 0; j < A.size(); j++){
                if(A[j] == M[nx][ny])
                    j = A.size() + 2;
            }
            if(j != A.size() + 2)
                A.push_back(M[nx][ny]);
        }
    }
}


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,m;
    char x;

    fin >> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            fin >> x;
            if(x == '1')
                M[i][j] = -1;
        }

    for(int i = 0; i <= n + 1; i++)
        M[i][0] = M[i][m + 1] = -1;
    for(int j = 0; j <= m + 1; j++)
        M[0][j] = M[n + 1][j] = -1;

    int camere = 0,ariemax = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){

        if(M[i][j] == 0)
            Fill(++camere,i,j);

        if(V[camere] > ariemax)
            ariemax = V[camere];

        }
    }
    int S = 0,s,xx,yy;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
        if(M[i][j] == -1){
            s = 0;
            cauta(i,j);
            for(int k = 0; k < A.size(); k++)
                s += V[A[k]];
            if(s > S){
                S = s;
                xx = i;  yy = j;
            }
            A.clear();
        }

    }


    fout << camere << "\n" << ariemax << "\n" << xx << " " << yy <<" "<< S;

    return 0;
}