Cod sursa(job #719832)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 22 martie 2012 09:28:56
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <utility>
#include <queue>
using namespace std;
vector < queue< pair<int,int> > > lista(22520);
int N, M, start, a[151][151], nr;
bool vizA[151][151], viz[22520];

inline int poz( pair <int,int> aux) {
	return (aux.first-1)*M + aux.second;
}

void lee(int i, int j) {
	int d[4] = {0, 0, 1, -1};
	int d1[4] = {1, -1, 0, 0};
	queue < pair<int,int> > coada;
	coada.push( make_pair(i, j) );
	for (; !coada.empty(); coada.pop()) {
		for (int i = 0; i < 4; ++i) {
			pair <int, int> aux = coada.front();
			aux.first += d[i];
			aux.second += d1[i];
			
			if (0 < aux.first && aux.first <= N && 0 < aux.second && aux.second <= M) {
				if (!vizA[aux.first][aux.second]) {
					if ( viz[ a[aux.first][aux.second] ] ) {
						vizA[aux.first][aux.second] = true;
						viz[ poz(aux) ] = true;
						
						for (; !lista[poz(aux)].empty(); lista[poz(aux)].pop()) {
							coada.push( lista[poz(aux)].front() );
							viz[poz(lista[poz(aux)].front())] = true;
							vizA[lista[poz(aux)].front().first][lista[poz(aux)].front().second] = true;
						}
						
						coada.push( aux );
					} else {
						lista[ a[aux.first][aux.second] ].push(aux);
					}
				}
			}
		}
	}
}

inline int linie(int start) {
	return start/M+1;
}

inline int coloana(int start) {
	return ((start == M)?M:start%M);
}
int main() {
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	
		scanf("%d %d %d", &N, &M, &start);
		
		for (int i = 1 ; i <= N; ++i) {
			for (int j = 1; j <= M; ++j) {
				scanf("%ld", &a[i][j]);
			}
		}
		
		viz[ a[linie(start)][coloana(start)] ] = true;
		vizA[linie(start)][coloana(start)] = true;
		lee(linie(start), coloana(start));
		
		for (int i = 1; i <= N*M; ++i) {
			nr += viz[i];
		}
		
		printf("%d\n", nr);
	
	return 0;
}