Cod sursa(job #2315702)

Utilizator skoda888Alexandru Robert skoda888 Data 10 ianuarie 2019 14:15:43
Problema Castel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb

#include <iostream>
#include <fstream>
#include <queue>
#include <set>
#include <vector>

const int MNMAX = 151;

struct Camera{
    int numar;
    int cheie_necesara;
};

struct Coord{
    int i;
    int j;
};


int N, M, K;

const int row[4] = {1, 0, -1, 0};
const int col[4] = {0, 1, 0, -1};

std::set<int> chei_disp;
std::vector<Coord> CamereInchise[MNMAX];
Coord Start;
Camera castel[MNMAX][MNMAX];
std::queue<Coord> Camere;
bool viz[MNMAX][MNMAX];

bool interior(Coord A){
    return (A.i > 0 && A.i <= N && A.j > 0 && A.j <= M);
}

int BFS(){

    int countR = 0;

    do{
        Coord curr_node = Camere.front();
        viz[curr_node.i][curr_node.j] = true;
        std::cout << curr_node.i << ' ' << curr_node.j << '\n';
        ++countR;
        Camere.pop();

        for(int dir = 0; dir <= 3; ++dir){
            Coord tmp = {curr_node.i + row[dir], curr_node.j + col[dir]};

            if(interior(tmp) && !viz[tmp.i][tmp.j]){
                if(chei_disp.find(castel[tmp.i][tmp.j].cheie_necesara) != chei_disp.end()){
                    Camere.push(tmp);
                    viz[tmp.i][tmp.j] = true;
                    chei_disp.insert(castel[tmp.i][tmp.j].numar);
                    for(int i = 0; i < CamereInchise[castel[tmp.i][tmp.j].numar].size(); ++i){
                        if(!viz[CamereInchise[castel[tmp.i][tmp.j].numar][i].i][CamereInchise[castel[tmp.i][tmp.j].numar][i].j]){
                            Camere.push(CamereInchise[castel[tmp.i][tmp.j].numar][i]);
                            viz[CamereInchise[castel[tmp.i][tmp.j].numar][i].i][CamereInchise[castel[tmp.i][tmp.j].numar][i].j] = true;
                        }
                    }
                }
                else{
                    CamereInchise[castel[tmp.i][tmp.j].cheie_necesara].push_back(tmp);
                }
            }
        }

    }while(!Camere.empty());

    return countR;
}


int main(){

    std::ifstream in("castel.in");
    std::ofstream out("castel.out");

    in >> N >> M >> K;

    ///Calculez coordonatele camerei de start
    int col = K % M;
    Start.i = (col == 0) ? K / M : K / M + 1;
    Start.j = (col == 0) ? M : col;
    Camere.push(Start);
    chei_disp.insert(K);

    ///Citesc cheile necesare deschiderii castelului
    int k = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= M; ++j){
            in >> castel[i][j].cheie_necesara;
            castel[i][j].numar = ++k;
        }
    }

    out << BFS();

    return 0;
}