Cod sursa(job #2534451)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 30 ianuarie 2020 16:28:25
Problema Castel Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int n, m, k, i, j;
int usa[151][151];
int cheie[151][151], c;
bool cheie_gasita[22501];
bool u[151][151];
int rez;

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

bool ok(int x, int y)
{
    return (x>=1 && x<=n && y>=1 && y<=m);
}

int main()
{
    f >> n >> m >> k;
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            f >> usa[i][j];
            cheie[i][j] = ++c;
        }

    int poz1 = k/m + (k%m > 0);
    int poz2 = k%m + m*(k%m == 0);

    int x, y;
    int xx, yy;
    bool gata=0;

    u[poz1][poz2] = 1;
    cheie_gasita[cheie[poz1][poz2]] = 1;

    queue < pair < int, int > > cu_cheie, fara_cheie, aux;
    cu_cheie.push(make_pair(poz1, poz2));

    while (!gata)
    {
        /*for (i=1;i<=n*m;i++)
            if (cheie_gasita[i])
                g<<i<<" ";
        g<<"\n";*/

        if (cu_cheie.empty())
            gata=1;
        else
            while (!cu_cheie.empty())
            {
                x = cu_cheie.front().first;
                y = cu_cheie.front().second;
                //g << x << " " << y <<"\n";
                cu_cheie.pop();
                rez++;
                for (i=0; i<4; i++)
                {
                    xx = x + dx[i];
                    yy = y + dy[i];
                    if (ok(xx, yy) && !u[xx][yy])
                    {
                        u[xx][yy] = 1;
                        if (cheie_gasita[usa[xx][yy]])
                        {
                            cheie_gasita[cheie[xx][yy]] = 1;
                            cu_cheie.push(make_pair(xx, yy));
                        }
                        else
                            fara_cheie.push(make_pair(xx, yy));
                    }
                }
            }

        //g<<"\n";
        while (!fara_cheie.empty())
        {
            x = fara_cheie.front().first;
            y = fara_cheie.front().second;
            if (cheie_gasita[usa[x][y]])
            {
                cu_cheie.push(make_pair(x, y));
                cheie_gasita[cheie[x][y]]=1;
            }
            else
                aux.push(make_pair(x, y));
            fara_cheie.pop();
            //g<<x<<" "<<y<<"\n";
        }

        while (!aux.empty())
        {
            x = aux.front().first;
            y = aux.front().second;
            fara_cheie.push(make_pair(x, y));
            aux.pop();
        }

        //g<<"\n\n";
    }

    g << rez;

    return 0;
}