Cod sursa(job #55587)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 27 aprilie 2007 21:34:39
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#define FIN "castel.in"
#define FOUT "castel.out"
#define MAX 200
#define __debug__ 0

struct list {
	long x;
	list *l;
} * A[MAX*MAX];
struct queue {
	long x,y;
	queue *l;
} *p, *u;

void add(long x, long i) {
	list *temp = new list;
	temp -> l = A[i]; 
	temp -> x = x;
	A[i] = temp;
}

long dx[] = {1,0,-1,0};
long dy[] = {0,1,0,-1};

long n,m,k,nr;
bool acces[MAX*MAX], U[MAX][MAX];

inline long index(long x, long y) {
	return (x-1)*m+y;
}

void make(long x) { 
	if ( __debug__ ) {
		long i,j;
		if ( x%m==0 )
			j = m;
		else
			j = x%m;
		i = (x-j)/m + 1;
		fprintf(stderr, "%2ld %2ld este acum accesibil\n", i,j);
	}
	acces[x] = true;
	list *p;
	for (p=A[x]; p; p=p->l) 
		make( p->x );
}

void add_q(long x, long y) {
	U[x][y] = true;
	queue *temp = new queue;
	temp -> x = x;
	temp -> y = y;
	temp -> l = 0;
	if (u) 
		u->l = temp;
	u = temp;
}

void lee() {
	long i,j, dep;
	
	if ( k%m==0 ) 
		j =	m;
	else
		j = k%m;
	i = (k-j)/m+1;
	add_q(i,j);
	for (p=u; p; p=p->l) {
		nr++;
		if ( __debug__ )
			fprintf(stderr, "Debug: %ld %ld\n", p->x, p->y);
		for (dep=0; dep<4; ++dep) {
			i = p->x + dx[dep];
			j = p->y + dy[dep];
			if ( i<1 || j<1 || i>n || j>m )
				continue;
			if ( acces[index(i,j)] && !U[i][j] )
				add_q(i,j);
		}
	}
}

int main() {
	long i,j,x;

	freopen(FIN, "r", stdin);
	scanf("%ld %ld %ld", &n,&m, &k);
	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j) {
			scanf("%ld", &x);
			if ( x!= index(i,j) ) 
				add( index(i,j), x );
		}	
	fclose(stdin);

	for (i=1; i<=n; ++i)
		for (j=1; j<=m; ++j)
			U[i][j] = acces[index(i,j)] = false;
	
	make(k);
	lee();

	freopen(FOUT, "w", stdout);
	printf("%ld\n", nr);
	fclose(stdout);
	return 0;
}