Pagini recente » Cod sursa (job #2157337) | Cod sursa (job #1559371) | Cod sursa (job #2117014) | Cod sursa (job #1759676) | Cod sursa (job #2315702)
#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;
}