Pagini recente » Cod sursa (job #2752277) | Monitorul de evaluare | Cod sursa (job #1565596) | Cod sursa (job #2022747) | Cod sursa (job #1563879)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 157;
int N, M, start_room;
int A[MAX_N * MAX_N], cod[MAX_N][MAX_N];
vector<int>vec[MAX_N * MAX_N];
vector<int>vec2[MAX_N * MAX_N];
bool canuse(int x, int y) {
return x > 0 && y > 0 && x<=N && y <=M;
}
const int vecX[] = {-1, 0, 1, 0};
const int vecY[] = {0, 1, 0, -1};
void Read() {
ifstream fin("castel.in");
fin >> N >> M >> start_room;
for(int i=1; i <= N * M; ++i)
fin >> A[i],vec2[A[i]].push_back(i);
int tmp = 1;
for(int i=1; i <= N; ++i)
for(int j=1; j <= M; ++j)
cod[i][j] = tmp++;
tmp = 1;
for(int i=1; i <= N; ++i)
for(int j=1; j <= M; ++j) {
for(int k=0; k < 4; ++k) {
int ni = i + vecX[k], nj = j + vecY[k];
if(canuse(ni, nj)) vec[tmp].push_back(cod[ni][nj]);
}
++tmp;
}
}
bool fols[MAX_N * MAX_N];
void Solve() {
unordered_map<int, int>keys;
keys[start_room] = 1;
queue<int>q; q.push(start_room); fols[start_room] = 1;
while(!q.empty()) {
int act = q.front(); q.pop();
for(int son : vec[act]) {
int key_req = A[son];
if(keys.find(key_req) != keys.end() && fols[son] == 0) {
fols[son] ++;
q.push(son);
if(keys.find(son) == keys.end()) keys.insert({son, 1});
}
}
if(!vec2[act].size()) continue;
for(auto l =vec2[act].begin();l!=vec2[act].end();++l) {
if(fols[*l]) continue;
bool canHere = 0;
for(int j : vec[*l]) {
if(fols[j]) {canHere = 1; break;}
}
if(canHere){
q.push(*l);
fols[*l]=1;
if(keys.find(*l)==keys.end())keys.insert({*l, 1});
if(vec2[act].size()==0) break;
}
}
}
int folst = 0;
for(int i=1; i <= N*M; ++i)
folst += fols[i] != 0;
cout << folst;
}
int main() {
Read();
Solve();
return 0;
}