Cod sursa(job #382608)

Utilizator klamathixMihai Calancea klamathix Data 14 ianuarie 2010 08:45:31
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<cstdio>
#include<queue>
#include<bitset>
#define f first
#define s second
#define maxn 160
using namespace std;

int dir1[5] = { 0 , 0 , 1 , -1};
int dir2[5] = { 1 , -1 , 0 , 0};

int i , j , A[maxn][maxn] , result , n , m , init;
int seen[maxn][maxn];
pair <int , int> start;
bool key[maxn * maxn];

int code ( int i , int j ) {
	return ( i - 1 ) * m + j;
}

void BFS()
{
	int k;
	pair <int , int > aux , act;
	queue < pair <int , int > > Q;
	while (!Q.empty()) Q.pop();
	
	Q.push(start);
	
	while ( !Q.empty() ) {
		aux = Q.front(), Q.pop();
		for( k = 0 ; k <= 3 ; ++k ) {
			act.f = aux.f + dir1[k];
			act.s = aux.s + dir2[k];
		if ( act.f >=1 && act.f <= n && act.s >=1 && act.s <= m )
			if ( seen[act.f][act.s] <= 4 )
				if ( key[A[act.f][act.s]] ) {
					if ( seen[act.f][act.s] == 0 )result++;
					key[code (act.f,act.s)] = 1;
					seen[act.f][act.s] += 1;
					Q.push(act);
				}
		}
	}
}
int main()
{
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	
	scanf("%d %d %d",&n,&m,&init);
	
	for( i = 1 ; i <= n ; ++i )
		for( j = 1 ; j <= m ; ++j )
			scanf("%d",&A[i][j]);
	
	start.f = init / m + 1;
	start.s = init % m;
	result = 1;
	seen[start.f][start.s] = 1;
	key[code(start.f, start.s)] = 1;	
	BFS();
	/*
	for ( i = 1 ; i <= n ; ++i ){
		for( j = 1 ; j <= m ; ++j )
			printf("%d",seen[i][j] );
		printf("\n");
	}
	*/
	printf("%d\n",result);
		
		
return 0;
}