Cod sursa(job #3000690)

Utilizator manudragoDragomir Manuel manudrago Data 12 martie 2023 18:57:50
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");
const int NMAX = 155;
int mat[NMAX][NMAX];
bool accesibil[NMAX * NMAX];
bool viz[NMAX * NMAX];
vector < int > opening[NMAX * NMAX];

int N, M, K;

void read(){
    fin >> M >> N >> K;
    for(int i = 1; i <= M; i++){
        for(int j = 1; j <= N; j++){
            fin >> mat[i][j];
        }
    }
}

int ij_to_val(int i, int j){
    return N * (i - 1) + j;
}

int my_ceil(int val){
    if(val % N == 0){
        return val / N;
    }
    return val / N  + 1;
}

pair < int, int > val_to_ij(int val){
    int i = my_ceil(val);
    int j;
    if(val % N == 0){
        j = N;
    }else{
        j = val % N;
    }
    return {i, j};
}

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

queue < int > q;

bool is_valid(int inou, int jnou){
    if(inou < 1 || jnou < 1 || inou > M || jnou > N){
        return false;
    }
    return true;
}

void solve(){
    q.push(K);
    accesibil[K] = true;
    viz[K] = true;

    while(!q.empty()){
        int cap = q.front();
        pair < int, int > pr = val_to_ij(cap);
        int i = pr.first;
        int j = pr.second;
        q.pop();

        /// ma duc pe vecini
        for(int k = 0; k < 4; k++){
            int inou = i + dx[k];
            int jnou = j + dy[k];
            if(is_valid(inou, jnou)){
                int val = ij_to_val(inou, jnou);
                if(!viz[val]){
                    if(accesibil[mat[inou][jnou]]){
                        q.push(val);
                        accesibil[val] = 1;
                        viz[val] = 1;
                    }else{
                        opening[mat[inou][jnou]].push_back(val);
                    }
                }
            }
        }

        /// accesibile din alte parti
        for(auto el: opening[cap]){
            if(!viz[el]){
                q.push(el);
                viz[el] = 1;
                accesibil[el] = 1;
            }
        }

    }
}

int main()
{
    read();
    solve();
    int accesibile = 0;
    for(int i = 1; i <= N * M; i++){
        if(accesibil[i]){
            accesibile++;
        }
    }
    fout << accesibile;
    return 0;
}