Cod sursa(job #1222190)

Utilizator pulseOvidiu Giorgi pulse Data 22 august 2014 15:39:03
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int MAXN = 155;
const int Dx[] = {-1, 0, 1, 0};
const int Dy[] = {0, 1, 0, -1};
int M, N, K, X, Y, iv, jv;
bool Key[MAXN], Used[MAXN][MAXN];
struct Mat
{
	int x;
	int y;
} a[MAXN][MAXN], Q[MAXN * MAXN];

bool OK(int i, int j)
{
	if (i < 1 || i > M || j < 1 || j > N) return 0;
	if (Used[i][j] || !Key[a[i][j].x]) return 0;
	return 1;
}

int Lee()
{
	int l, r;
	l = r = 1;
	Q[l].x = X;
	Q[l].y = Y;
	Used[X][Y] = 1;
	Key[K] = 1;
	bool Ok = 1;
	int i, j, ans = 1;
	while (Ok)
	{
		for (l = 1, Ok = 0; l <= r; ++l)
		{
			int i = Q[l].x;
			int j = Q[l].y;
			for (int d = 0; d < 4; ++d)
			{
				iv = i + Dx[d];
				jv = j + Dy[d];
				if (OK(iv, jv))
				{
					Q[++r].x = iv;
					Q[r].y = jv;
					Used[iv][jv] = 1;
					Key[a[iv][jv].y] = 1;
					++ans;
					Ok = 1;
				}
			}
		}
	}
	return ans;
}

int main()
{
	freopen("castel.in", "r", stdin);
	freopen("castel.out", "w", stdout);
	scanf("%d %d %d\n", &M, &N, &K);
	int cnt = 0;
	for (int i = 1; i <= M; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			++cnt;
			scanf("%d", &a[i][j].x);
			a[i][j].y = cnt;
			if (K == cnt)
			{
				X = i;
				Y = j;
			}
		}
	}
	printf("%d\n", Lee());
	return 0;
}