Cod sursa(job #3030782)

Utilizator tudorp_Pop Tudor tudorp_ Data 17 martie 2023 21:11:40
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

int n, m, k, ist, jst, di[] = { -1,0,1,0 }, dj[] = { 0,1,0,-1 };
int mat[155][155];
bool cheie[2355];
bool acces[2355];
vector<int>ghiozdan[2355];

bool inmat(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

pair < int, int > cordon(int val) {
    int i;
    int j;
    if (val % m == 0) {
        i = val / m;
        j = m;
    }
    else {
        i = val / m + 1;
        j = val % m;
    }
    return { i, j };
}

int back_to_val (int i, int j) {
    return m * (i - 1) + j;
}

queue<int>q;

void solve()
{
    q.push(k);
    cheie[k] = 1;
    acces[k] = 1;
    while (!q.empty())
    {
        pair<int, int>p;
        int varf = q.front();
        p = cordon(varf);
        q.pop();
        for (int x = 0; x <= 3; x++)
        {
            int iv = p.first + di[x],jv = p.second + dj[x];
            if (inmat(iv, jv))
            {
                int nr = back_to_val(iv, jv);
                ///daca n-am vizitat-o
                if (!cheie[nr])
                {
                    ///daca avem acces la acest loc
                    if (acces[mat[iv][jv]] == 1)
                    {
                        ///primim acces nou
                        acces[nr] = 1;
                        cheie[nr] = 1;
                        q.push(nr);
                    }
                    else
                    {
                        ///il bagam in buzunar daca nu
                        ghiozdan[mat[iv][jv]].push_back(nr);
                    }
                }
            }
        }
        ///cautam in ghiozdan
        for (auto it : ghiozdan[varf])
        {
            if (!cheie[it])
            {
                q.push(it);
                cheie[it] = 1;
                acces[it] = 1;
            }
        }
    }
}

int main()
{
    f >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            f >> mat[i][j];
        }
    }
    solve();
    int tot = 0;
    for (int i = 1; i <= n*m; i++)
    {
        if (acces[i])
        {
            tot++;
        }
    }
    g << tot;
}