Cod sursa(job #86341)

Utilizator gcosminGheorghe Cosmin gcosmin Data 24 septembrie 2007 12:13:12
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define NMAX 160

int N, M, K;

int a[NMAX][NMAX];

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

vector <int> poz[NMAX * NMAX];

int p, q;
int coada[NMAX * NMAX];
char viz[NMAX][NMAX];

char key[NMAX * NMAX];

inline void get_xy(int K, int &x, int &y)
{
	x = (K - 1) / M + 1;
	y = (K - 1) % M + 1;
}

inline int get_poz(int x, int y)
{
	return (x - 1) * M + y;
}

void dump(int k)
{
	vector <int> :: iterator it;
	
	for (it = poz[k].begin(); it != poz[k].end(); ++it) {
		key[*it] = 1;
		coada[++q] = *it;
		
		dump(*it);
	}
}

int main()
{
	int i, j;
	
	freopen("castel.in", "r", stdin);
	freopen("castel.out", "w", stdout);

	scanf("%d %d %d", &N, &M, &K);
	
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++) scanf("%d", &a[i][j]);	
		
	int x, y;
	
	coada[0] = K;
	key[K] = 1;
	p = 0, q = 0;
	
	vector <int> :: iterator it;
	int xx, yy;
	while (p <= q) {
		get_xy(coada[p], x, y);
		
		viz[x][y] = 1;
		p++;
		
		for (i = 0; i < 4; i++) {
			xx = x + dx[i];
			yy = y + dy[i];
			
			if (!(1 <= xx && xx <= N && 1 <= yy && yy <= M)) continue;
			if (viz[xx][yy]) continue;
			
			viz[xx][yy] = 1;
			
			if (key[ a[xx][yy] ]) {
				coada[++q] = get_poz(xx, yy);
				key[ coada[q] ] = 1;
				dump( coada[q] );
			} else poz[ a[xx][yy] ].push_back( get_poz(xx, yy) );
		}
	}
	
	printf("%d\n", q + 1);
	
return 0;
}