Pagini recente » Cod sursa (job #2196016) | Cod sursa (job #192144) | Cod sursa (job #410220) | Cod sursa (job #1469638) | Cod sursa (job #980157)
Cod sursa(job #980157)
#include <iostream>
#include <cstdio>
#include <ctime>
#define NMax 150
using namespace std;
const int dx[] = {-1,0,1, 0},
dy[] = { 0,1,0,-1};
struct Nod{ int l, c;};
Nod *C, *Aux, x, y;
int a[NMax+2][NMax+2];
char viz[NMax+2][NMax+2];
bool uz[NMax*NMax+1];
int n, m, k;
int IncC, SfC;
int IncAux, SfAux, SfAcum;
int Key;
void _Read();
void _Solve();
inline Nod _top();
inline void _pop();
void PrintArray();
inline void _push(Nod x);
inline void _PrintSol(void);
inline int _getKey(Nod p);
inline void _getPoz(Nod& p, int Key);
int main()
{
//double ti, tf;
//ti = clock();
freopen("castel.in", "rt", stdin);
freopen("castel.out", "wt", stdout);
_Read();
_Solve();
_PrintSol();
//tf = clock();
//printf ("\n\ntime = %.4lf\n\n", (tf-ti)/CLK_TCK);
fclose(stdin);
fclose(stdout);
return 0;
}
void _Read()
{
scanf("%d%d%d", &n, &m, &k);
int i, j;
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
}
/// bordarea matricii
for (i = 0; i <= n+1; ++i)
{
viz[i][0] = viz[i][m+1] = 3;
}
for (i = 1; i <= m; ++i)
{
viz[0][i] = viz[n+1][i] = 3;
}
}
void PrintArray()
{
int i, j;
printf("\n\n");
for (i = 0; i <= n+1; ++i)
{
for (j = 0; j <= m+1; ++j)
printf("%3d", viz[i][j]);
printf("\n");
}
}
void _Solve()
{
IncC = SfC = 0;
IncAux = SfAux = 0;
C = new Nod[n*m];
Aux = new Nod[n*m];
/// marchez cheia k
_getPoz(x,k);
uz[k] = true;
uz[a[x.l][x.c]] = true;
viz[x.l][x.c] = 1;
_push(x);
bool ok;
do {
ok = false;
while (IncC < SfC)
{
x = _top(); _pop();
//printf("%d %d %d\n", x.l, x.c, _getKey(x));
for (int k = 0; k < 4; ++k)
{
y.l = x.l+dx[k];
y.c = x.c+dy[k];
if (viz[y.l][y.c] == 0 || viz[y.l][y.c] == 2)
{
int key = _getKey(y);
//printf("%d %d %d\n", y.l, y.c, _getKey(y));
if (uz[a[y.l][y.c]] or uz[key])
{
//printf("%d %d %d\n", y.l, y.c, _getKey(y));
uz[key] = true;
uz[a[y.l][y.c]] = true;
viz[y.l][y.c] = 1;
_push(y);
}
else { viz[y.l][y.c] = 2; Aux[SfAux++] = y; }
}
}
}
for (IncAux = SfAcum = 0; IncAux < SfAux; ++IncAux)
{
y = Aux[IncAux];
if (viz[y.l][y.c] != 1) {
if (uz[_getKey(y)] or uz[a[y.l][y.c]])
{
uz[_getKey(y)] = 1;
uz[a[y.l][y.c]] = 1;
viz[y.l][y.c] = 1;
_push(y);
ok = true;
}
else { Aux[SfAcum++] = y; }
}
}
SfAux = SfAcum;
} while (ok);
}
inline void _PrintSol(void)
{
printf("%d\n", SfC);
}
inline void _push(Nod x)
{
C[SfC++] = x;
}
inline Nod _top()
{
return C[IncC];
}
inline void _pop()
{
IncC++;
}
inline void _getPoz(Nod& p, int Key)
{
p.l = (Key-1)/m+1;
p.c = (Key-1)%m+1;
}
inline int _getKey(Nod p)
{
return (m*(p.l-1)+p.c);
}