Pagini recente » Cod sursa (job #507678) | Cod sursa (job #668350) | Cod sursa (job #2616180) | Cod sursa (job #2820681) | Cod sursa (job #59717)
Cod sursa(job #59717)
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
#define MAX 152
const int di[] = { -1, 0, 1, 0 };
const int dj[] = { 0, 1, 0, -1 };
struct stare {
int i, j;
};
stare aux;
int n, m, k, val;
int rez = 0;
int a[MAX][MAX];
bool has_key[MAX];
bool marked[MAX][MAX];
void bfs();
int get_line(int room);
int get_col(int room);
int get_room(int i, int j);
int main()
{
FILE *fin = fopen("castel.in", "r");
FILE *fout = fopen("castel.out", "w");
fscanf(fin, "%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
fscanf(fin, "%d", &a[i][j]);
bfs();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (marked[i][j])
rez++;
fprintf(fout, "%d\n", rez);
fclose(fin);
fclose(fout);
return 0;
}
void bfs()
{
int ii, jj, inou, jnou;
stare curr;
queue<stare> Q;
aux.i = get_line(k);
aux.j = get_col(k);
Q.push(aux);
has_key[k] = true;
has_key[a[aux.i][aux.j]] = true;
marked[aux.i][aux.j] = true;
while (!Q.empty())
{
curr = Q.front();
Q.pop();
ii = curr.i;
jj = curr.j;
for (int d = 0; d < 3; ++d)
{
inou = ii + di[d];
jnou = jj + dj[d];
if (inou >= 1 && jnou >= 1 && inou <= n && jnou <= m)
if (has_key[ a[inou][jnou] ] && !marked[inou][jnou])
{
marked[inou][jnou] = true;
has_key[ get_room(inou, jnou) ] = true;
for (int iii = 1; iii <= n; ++iii)
for (int jjj = 1; jjj <= m; ++jjj)
if (marked[iii][jjj])
{
aux.i = iii;
aux.j = jjj;
Q.push(aux);
}
}
}
}
}
inline int get_line(int room)
{
return ((room-1) / n) + 1;
}
inline int get_col(int room)
{
return (room - (get_line(room) - 1) * n) % (m + 1);
}
inline int get_room(int i, int j)
{
return (i-1) * m + j;
}