Cod sursa(job #296567)

Utilizator katakunaCazacu Alexandru katakuna Data 4 aprilie 2009 22:16:58
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
using namespace std;
#include <cstdio>
#include <vector>
#include <deque>
#include <algorithm>

#define Nmax 152

int n, m, i, j, l, c, x ,y, nr, k, p;
deque < pair <int, int>  > q;
vector < pair <int, int> > L[Nmax * Nmax];
int a[Nmax][Nmax], viz[Nmax * Nmax];
int d[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};

int main(){

	FILE *f = fopen("castel.in", "r");
	FILE *g = fopen("castel.out", "w");
	
	fscanf(f,"%d %d %d",&n, &m, &p);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			fscanf(f,"%d",&a[i][j]);
	
	x = (p-1)/m + 1; y = (p-1)%m + 1;
	q.push_back( make_pair(x, y) );
	a[x][y] = -1; 
	viz[p] = 1;
	nr = 1;
	
	while( !q.empty() ){
		l = q.front().first; c = q.front().second;
		
		k = (l - 1)*m + c;
		for(j = 0; j < (int)L[k].size(); j++){
			x = L[k][j].first; y = L[k][j].second;
			nr++; viz[(x - 1) * m  + y] = 1;
			q.push_back(make_pair(x, y));
		}
		
		for(i = 0; i <= 3; i++){
			x = l + d[0][i];
			y = c + d[1][i];
			k = (x - 1) * m  + y;
			
			if( x > 0 && y > 0 && x <= n && y <= m && a[x][y] != -1){
				if( viz[ a[x][y] ] ){
					nr++; viz[k] = 1; a[x][y] = -1;
					q.push_back( make_pair(x, y) );
				}
				
				else{
					L[ a[x][y] ].push_back( make_pair(x, y) );
					a[x][y] = -1;
				}
			}
			
		}		
		
		q.pop_front();
	}
	
	fprintf(g,"%d",nr);
	
	fclose(f);
	fclose(g);

	return 0;
}