Cod sursa(job #2813169)

Utilizator MariusDinsorea32DinsoreanMarius MariusDinsorea32 Data 5 decembrie 2021 21:53:58
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

const int N = 156;
const int ox[] = {0, 1, 0, -1};
const int oy[] = {1, 0, -1, 0};

queue <int> q;
vector <int> key[100009];

int n, m, x, i, j, z, coord, l, c, ln, cn, rez;

bool used[N * N], acces[N * N];

int need[N][N], linie[N], coloana[N], v, nev, cheie;

bool inside(int a, int b)
{
    if(a <= n && a >= 1 && b <= m && b >= 1) return true;
    return false;
}

int camera(int a, int b)
{
    return (a - 1) * m + b;
}

int main()
{
    fin >> n >> m >> x;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            fin >> need[i][j], linie[camera(i, j)] = i, coloana[camera(i, j)] = j;
    q.push(x);
    acces[x] = true;
    used[x] = true;
    while(!q.empty())
    {
        v = q.front();
        l = linie[v];
        c = coloana[v];
        acces[v] = true;
        for(i = 0; i < 4; i++)
        {
            ln = l + ox[i];
            cn = c + oy[i];
            nev = need[ln][cn];
            cheie = camera(ln, cn);
            if(inside(ln, cn) && !used[cheie])
            {
                if(acces[nev])
                {
                    used[cheie] = true;
                    q.push(cheie);
                }
                else key[nev].push_back(cheie);
            }
        }
        for(i = 0; i < key[v].size(); i++)
        {
            if(!used[key[v][i]])
            {
                used[key[v][i]] = true;
                q.push(key[v][i]);
            }
        }
        q.pop();
    }
    for(i = 1; i <= n * m; i++) rez += acces[i];
    fout << rez;
    return 0;
}