Cod sursa(job #292310)

Utilizator cristiprgPrigoana Cristian cristiprg Data 30 martie 2009 23:31:42
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#define DIM 155


int a[DIM][DIM], m, n, k, b[DIM][DIM];

void citire()
{
	FILE *f = fopen("castel.in", "r");
	fscanf(f, "%d%d%d", &m, &n, &k);
	for(int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			fscanf(f, "%d", &a[i][j]);


	fclose(f);
}

int OK(int i, int j)
{
	if (i < 1 || i > m || j < 1 || j > n)
		return 0;

	if (b[i][j] == -1)
		return 0;


	return 1;
}

int camera(int i, int j)
{
	return (i - 1) * n + ((j % n == 0)? n : (j%n));
}

void solve()
{
	int i, j, im, jm, chei[DIM * DIM], nr_chei = 1, coada[2][DIM * DIM], st, dr;
	const int vi[] = {-1, 0, 1, 0}, vj[] = {0, 1, 0, -1};
	st = dr = 1;
	i = k / n + 1;
	j = k % n;
	if (j == 0)
		j = n;

	coada[0][1] = i;
	coada[1][1] = j;

	chei[nr_chei] = k;

	int gasit = 0;
	b[i][j] = -1;
	while(1)
	{
	  gasit = 0;
	  for (int cheie = 1; cheie <= nr_chei; cheie++)

		for (st = 1; st <= dr; st++)
		{
			i = coada[0][st];
			j = coada[1][st];
			b[i][j] = -1;
			for (int d = 0; d < 4; d++)
			{
				im = i + vi[d];
				jm = j + vj[d];

				if (OK(im, jm ))
					if (chei[cheie] == a[im][jm])
					{
						gasit = 1;
						dr++;


						coada[0][dr] = im;
						coada[1][dr] = jm;
						chei[++nr_chei] = camera(im, jm);
						b[im][jm] = -1;
					}
			}
		}


		if (!gasit)
		{
			FILE *f = fopen("castel.out", "w");
			fprintf(f, "%d\n", dr);
			fclose(f);
			return ;
		}


	}

}

int main()
{
	citire();
	solve();

	return 0;
}