Cod sursa(job #3343319)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 26 februarie 2026 21:46:19
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

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

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

bitset<DMAX * DMAX + 1> F; /// F[i] = 1, daca camera i este accesibila
bitset<DMAX + 1> viz[DMAX + 1];
int key[DMAX + 1][DMAX + 1];
int m, n, k;

struct poz
{
    int x, y;
};
poz pstart, crt, vec;
vector<poz> Q;

inline bool inside(poz p)
{
    return p.x >= 1 && p.x <= m && p.y >= 1 && p.y <= n;
}

poz get_poz(int idx)
{
    poz p;
    p.x = (idx + n - 1) / n;
    p.y = idx - (p.x - 1) * n;
    return p;
}

inline int get_idx(poz p)
{
    return (p.x - 1) * n + p.y;
}

void citire()
{
    f >> m >> n >> k;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            f >> key[i][j];
}

void init()
{
    pstart = get_poz(k);
    F[get_idx(pstart)] = 1;
    F[key[pstart.x][pstart.y]] = 1;
    viz[pstart.x][pstart.y] = 1;
    Q.push_back(pstart);
}

bool Lee()
{
    bool ok = 0;
    for(int i = 0; i < (int)Q.size(); i++)
    {
        crt = Q[i];
        for(int i = 0; i < 4; i++)
        {
            vec.x = crt.x + dx[i];
            vec.y = crt.y + dy[i];
            if(inside(vec) && F[key[vec.x][vec.y]] == 1 && !viz[vec.x][vec.y])
            {
                ok = 1;
                Q.push_back(vec);
                F[get_idx(vec)] = 1;
                viz[vec.x][vec.y] = 1;
            }
        }
    }
    return ok;
}

void nr_camere()
{
    int nr = 0;
    for(int i = 1; i <= m; i++)
        nr += viz[i].count();
    g << nr;
}

int main()
{
    citire();
    init();
    while(Lee())
        ;
    nr_camere();
    f.close();
    g.close();
    return 0;
}