Pagini recente » Cod sursa (job #2844722) | Cod sursa (job #1509259) | Cod sursa (job #2562193) | Cod sursa (job #297571) | Cod sursa (job #3219463)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <queue>
#include <unordered_map>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
const int LMAX = 155;
int n, m;
bool inside(int i, int j) {
return i > 0 && i <= n && j > 0 && j <= m;
}
int dx[5] = {1, 0, -1, 0}, dy[5] = {0, 1, 0, -1};
vector<int> posrooms[24025];
int a[LMAX][LMAX], ans;
bool key[24025], viz[24025];
queue<int> Q;
void findrooms(int next) {
while (posrooms[next].size() > 0) {
int room = posrooms[next].back();
key[room] = true;
ans++;
Q.push(room);
findrooms(room);
posrooms[next].pop_back();
}
}
void bfs(int k) {
Q.push(k);
key[k] = true;
ans++;
viz[k] = true;
while (!Q.empty()) {
int room = Q.front();
Q.pop();
int i, j;
i = (room - 1)/m + 1;
j = (room - 1)%m + 1;
int l, c, next;
for (int dir = 0; dir < 4; dir++) {
l = i + dy[dir];
c = j + dx[dir];
next = c + (l-1)*m;
//fout<<next<<" ";
if (inside(l, c) && !viz[next]) {
if (key[a[l][c]]) { //daca am cheie pt vecin
key[next] = true;
ans++;
findrooms(next);
Q.push(next); //este posibila
}
else if (!viz[next]){ //nu am cheie pt asta momentan
posrooms[a[l][c]].push_back(next);//adaug camerele care s ar putea deschide daca capat cheia respectiva
}
viz[next] = 1;
}
}
}
}
int main() {
int k, i, j;
fin>>n>>m>>k;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
fin>>a[i][j];
}
}
bfs(k);
fout<<ans;
fin.close();
fout.close();
return 0;
}