Cod sursa(job #2316046)

Utilizator skoda888Alexandru Robert skoda888 Data 10 ianuarie 2019 22:32:20
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.37 kb


///Ideea: Un BFS normal, in care pot sa merg intr-o celula doar daca am gasit anterior cheia
///De fiecare data cand gasesc o noua cheie(adica merg intr-o noua celula), verific daca am pe "lista de asteptare"
///camere care pot fi deschide cu cheia gasita

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

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

struct Camera{
    int numar;
    int cheie_necesara;
};

struct Coord{
    int i;
    int j;
};

Coord Start;
int N, M, K;
Camera Camere[NMAX][NMAX];
bool viz[NMAX][NMAX];
std::queue<Coord> Coada;
bool CheiDisp[NMAX*NMAX];
std::vector<Coord> CamereIncuiate[NMAX*NMAX];


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

int BFS(){

    int countR = 0;

    do{
        Coord nod_curent = Coada.front();
        Coada.pop();

        for(int i = 0; i < CamereIncuiate[Camere[nod_curent.i][nod_curent.j].numar].size(); ++i){
            if(!viz[CamereIncuiate[Camere[nod_curent.i][nod_curent.j].numar][i].i][CamereIncuiate[Camere[nod_curent.i][nod_curent.j].numar][i].j]){
                Coada.push(CamereIncuiate[Camere[nod_curent.i][nod_curent.j].numar][i]);
                viz[CamereIncuiate[Camere[nod_curent.i][nod_curent.j].numar][i].i][CamereIncuiate[Camere[nod_curent.i][nod_curent.j].numar][i].j] = true;
            }
        }

        viz[nod_curent.i][nod_curent.j] = true;
        CheiDisp[Camere[nod_curent.i][nod_curent.j].numar] = true;
        //std::cout << nod_curent.i << ' ' << nod_curent.j << ' ' << Camere[nod_curent.i][nod_curent.j].cheie_necesara <<'\n';
        ++countR;

        //in care camere pot merge, in care nu?
        for(int dir = 0; dir < 4; ++dir){
            Coord tmp = {nod_curent.i + row[dir], nod_curent.j + col[dir]};

            if(interior(tmp) && !viz[tmp.i][tmp.j]){
                if(CheiDisp[Camere[tmp.i][tmp.j].cheie_necesara] == true){
                    Coada.push(tmp);
                    viz[tmp.i][tmp.j] = true;

                   // for(int i = 0; i < CamereIncuiate[Camere[tmp.i][tmp.j].numar].size(); ++i){
                    //    if(!viz[CamereIncuiate[Camere[tmp.i][tmp.j].numar][i].i][CamereIncuiate[Camere[tmp.i][tmp.j].numar][i].j]){
                   //         Coada.push(CamereIncuiate[Camere[tmp.i][tmp.j].numar][i]);
                    //        viz[CamereIncuiate[Camere[tmp.i][tmp.j].numar][i].i][CamereIncuiate[Camere[tmp.i][tmp.j].numar][i].j] = true;
                    //    }
                   // }
                }
                else{
                    CamereIncuiate[Camere[tmp.i][tmp.j].cheie_necesara].push_back(tmp);
                }
            }
        }

    }while(!Coada.empty());

    return countR;
}


int main(){

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

    ///CITIRE
    in >> N >> M >> K;

    int num = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= M; ++j){
            in >> Camere[i][j].cheie_necesara;
            Camere[i][j].numar = ++num;
        }
    }


    ///Calculez coordonatele camerei de start
    int col = K % M;
    Start.i = (col == 0) ? K / M : K / M + 1;
    Start.j = (col == 0) ? M : col;
    Coada.push(Start);
    CheiDisp[K] = true;

    ///BFS
    out << BFS();

    return 0;
}