Cod sursa(job #3000524)

Utilizator manudragoDragomir Manuel manudrago Data 12 martie 2023 15:58:07
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <unordered_set>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");
const int NMAX = 155;
int c[NMAX][NMAX];
int accesibile;
bool accesibil[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 >> c[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};

unordered_set < int > s;

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

bool is_accessible(int inou, int jnou){
    return accesibil[c[inou][jnou]];
}

void solve(){
    bool new_move;
    s.insert(K);
    accesibil[K] = 1;
    accesibile = 1;
    do{
        new_move = false;

        unordered_set < int > toadd;
        unordered_set < int > toerase;
        for(int el: s){
            bool can_be_further_explored = false;
            pair < int, int > prs = val_to_ij(el);
            int i = prs.first;
            int j = prs.second;

            for(int k = 0; k < 4; k++){
                int inou = i + dx[k];
                int jnou = j + dy[k];

                /// suntem in matrice
                if(is_valid(inou, jnou)){
                    int val = ij_to_val(inou, jnou);

                    /// putem ajunge pe acest element
                    if(is_accessible(inou, jnou)){
                        if(accesibil[val] == 0){
                            accesibil[val] = 1;
                            accesibile++;
                            toadd.insert(val);
                            new_move = true;
                        }
                    }else{
                        can_be_further_explored = true;
                    }
                }
            }
            if(!can_be_further_explored){
                toerase.insert(el);
            }
        }
        for(int el: toadd){
            s.insert(el);
        }
        for(int el: toerase){
            s.erase(el);
        }
    }while(!s.empty() && new_move);
}

int main()
{
    read();
    solve();
    fout << accesibile;
    return 0;
}