Pagini recente » Rezultatele filtrării | Cod sursa (job #123637)
Cod sursa(job #123637)
#include <cstdio>
#include <set>
using namespace std;
#define NMax 155
set <int> border;
int n, m, start, key[NMax][NMax], viz[NMax][NMax], keys[NMax*NMax], cam[NMax][NMax], startx, starty;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void read();
void solve();
int main()
{
read();
solve();
return 0;
}
void read()
{
int i, j;
FILE *fin = fopen("castel.in", "rt");
fscanf(fin, "%d %d %d", &n, &m, &start);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fscanf(fin, "%d", &key[i][j]);
cam[i][j] = (i-1) * m + j;
if ((i-1) * n + j == start)
{
startx = i;
starty = j;
}
}
}
void solve()
{
int go = 1, ok, i, j, x, k;
//std::_Tree<_Traits>::iterator it;
set<int>::iterator it;
keys[start] = 1;
viz[startx][starty] = 1;
for (k = 0; k < 4; k++)
border.insert(cam[startx+dx[k]][starty+dy[k]]);
while (go)
{
go = 0;
for (it = border.begin(),i=0; it != border.end(); it++)
{
x = *it;
if (keys[key[(x-1)/m+1][(x-1)%m+1]])
{
ok = 0;
for (k = 0; k < 4; k++)
if (viz[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]])
ok = 1;
if (ok)
{
viz[(x-1)/m+1][(x-1)%m+1] = 1;
keys[x] = 1;
border.erase(it);
it = border.begin();
for (k = 0; k < 4; k++)
{
if (border.find(cam[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]]) == border.end())
if(!viz[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]])
{
border.insert(cam[(x-1)/m+1+dx[k]][(x-1)%m+1+dy[k]]);
go = 1;
}
}
}
}
}
}
k = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
k += viz[i][j];
fprintf(fopen("castel.out", "wt"), "%d\n", k);
}