Pagini recente » Cod sursa (job #1098664) | Cod sursa (job #422087) | Cod sursa (job #2562550) | Cod sursa (job #1246570) | Cod sursa (job #861825)
Cod sursa(job #861825)
#include <cstdio>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
vector < queue < pair<int, int> > > v(22501);
queue < pair<int, int> > q;
int N, M, K, chei[22501], a[151][151], viz[151][151];
inline int indJ(int x) {
return ((x % M == 0)?M:(x%M));
}
inline int indI(int x) {
return (x-indJ(x))/M + 1;
}
inline bool daca_e_in_matrice( pair<int, int> x) {
if (x.first < 1) return false;
if (x.second < 1) return false;
if (x.first > N) return false;
if (x.second > M) return false;
return true;
}
inline bool daca_exista_cheie( int x) {
return (chei[x]==1);
}
void adauga_cheie( pair <int, int> z) {
int x = (z.first-1)*M + z.second;
if ( chei[x] == 1) return;
chei[x] = 1;
for (; !v[x].empty(); v[x].pop()) {
q.push( v[x].front() );
viz[v[x].front().first][v[x].front().second] = 1;
}
}
void incearca( pair <int, int> x) {
int d1[4] = {0, 1, 0, -1};
int d2[4] = {1, 0, -1, 0};
for (int i = 0; i < 4; ++i) {
pair <int, int> aux;
aux = x;
aux.first += d1[i];
aux.second += d2[i];
if (!daca_e_in_matrice(aux)) continue;
if (viz[aux.first][aux.second] == 1) continue;
if (daca_exista_cheie( a[aux.first][aux.second] )) {
viz[aux.first][aux.second] = 1;
adauga_cheie( aux );
q.push(aux);
} else {
v[a[aux.first][aux.second]].push(aux);
}
}
}
int main() {
freopen("castel.in", "r", stdin);
freopen("castel.out", "w", stdout);
scanf("%d %d %d", &N, &M, &K);
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
scanf("%d", &a[i][j]);
}
}
adauga_cheie( make_pair(indI(K), indJ(K)) );
viz[indI(K)][indJ(K)] = 1;
q.push( make_pair(indI(K), indJ(K)) );
for (; !q.empty(); q.pop() ) {
// printf( "%d\n", (q.front().first-1)*M+q.front().second );
incearca( q.front() );
}
int nr = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
nr += viz[i][j];
}
}
printf("%d\n", nr);
return 0;
}