Pagini recente » Cod sursa (job #1354776) | Cod sursa (job #2673380) | Cod sursa (job #2612246) | Cod sursa (job #1467216) | Cod sursa (job #2316003)
///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];
std::vector<Coord> CamereIncuiate[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();
viz[nod_curent.i][nod_curent.j] = true;
CheiDisp[Camere[nod_curent.i][nod_curent.j].numar] = true;
++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;
}