Cod sursa(job #2655716)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 5 octombrie 2020 12:47:03
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.81 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<utility>

using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

int n, m, k, val = 1;
int v[505][505], mask[505][505];
int tara[300001];

void scan()
{
    in >> k >> n >> m;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            in >> v[i][j];

            if(v[i][j] == 1)
                v[i][j] = -1;
        }
    }
}

bool ok(int ny, int nx)
{
    return(ny >= 0 && ny < n && 0 <= nx && nx < m);
}

int fillMat(int y, int x)
{
    queue<pair<int, int>> q;

    q.emplace(y, x);

    int cont = 0;

    while(!q.empty())
    {
        cont++;

        //cout << q.front().first << ' ' << q.front().second << '\n';

        for(int i = 0; i < 4; i++)
        {
            int x, y;
            if(i == 0)
            {
                x = 0;
                y = 1;
            }
            else
            {
                if(i == 1)
                {
                    x = 1;
                    y = 0;
                }
                else
                {
                    if(i == 2)
                    {
                        x = 0;
                        y = -1;
                    }
                    else
                    {
                        x = -1;
                        y = 0;
                    }
                }
            }

            int nx = q.front().second + x;
            int ny = q.front().first + y;

            if(ok(ny, nx) && mask[ny][nx] == 0 && v[ny][nx] != -1)
            {
                mask[ny][nx] = val;

                q.emplace(ny, nx);
            }
        }

        q.pop();
    }

    return cont;
}

void border(int y, int x)
{
    queue<pair<int, int>> q;

    q.emplace(y, x);

    while(!q.empty())
    {
        for(int i = 0; i < 4; i++)
        {
            int x, y;

            if(i == 0)
            {
                x = 0;
                y = 1;
            }
            else
            {
                if(i == 1)
                {
                    x = 1;
                    y = 0;
                }
                else
                {
                    if(i == 2)
                    {
                        x = 0;
                        y = -1;
                    }
                    else
                    {
                        x = -1;
                        y = 0;
                    }
                }
            }

            int nx = q.front().second + x;
            int ny = q.front().first + y;

            if(ok(ny, nx) && mask[ny][nx] != 0)
            {
                for(int j = 0; j < tara[mask[ny][nx]].len; j++)
                tara[mask[ny][nx]]++;
            }
            else
            {
                if(ok(ny, nx) && mask[ny][nx])
                    q.emplace(ny, nx);
            }
        }
    }
}

int main()
{
    scan();

    int maxArea = -1;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(ok(i, j))
            {
                mask[i][j] = val;

                maxArea = max(maxArea, fillMat(i, j));

                val++;
            }
        }
    }

    /*for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
            cout << mask[i][j] << ' ';

        cout << '\n';
    }

    cout << val-1 << '\n' << maxArea << '\n';*/

    if(k == 1)
    {
        out << maxArea << '\n';
        return 0;
    }


    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(v[i][j] == -1)
            {
                border(i, j);

            }
        }
    }

    int maxVec = -1;

    return 0;
}