Cod sursa(job #88733)

Utilizator tvladTataranu Vlad tvlad Data 3 octombrie 2007 17:54:39
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 151;
const int M = 151;

struct punct { int x,y,lvl; };

int n,m,st;
int rq[N][M];
bool reach[N][M];
bool newrch[N][M];

inline bool valid ( punct nx ) {
	return (0 <= nx.x && nx.x < n && 0 <= nx.y && nx.y < m &&
		!reach[nx.x][nx.y] && !newrch[nx.x][nx.y] &&
		reach[rq[nx.x][nx.y] / m][rq[nx.x][nx.y] % m]);
}

void bf() {
	queue<punct> q;
	queue<punct> nx;
	punct tmp = {st / m, st % m, 0};
	reach[tmp.x][tmp.y] = true;
	q.push(tmp);
	bool add = true;
	for (int lvl = 0; ; ) {
		if (q.empty()) {
			if (!add) break;
			lvl = (nx.front()).lvl;
//			printf("Schimbare de generatie dupa golire (a ajuns la %d):\n",lvl);
			add = false;
			while  (!nx.empty()) {
				punct a = nx.front(); nx.pop();
				q.push(a);
				reach[a.x][a.y] = true;
//				printf("%d %d (reach = %d)\n",a.x,a.y,reach[a.x][a.y]);
			}
//			printf("-----------\n");
		}
		punct a = q.front(); q.pop();
		if (a.lvl != lvl) {
			if (!add) break;
			lvl = a.lvl;
//			printf("Schimbare de generatie (a ajuns la %d):\n",lvl);
			add = false;
			while (!nx.empty()) {
				punct a = nx.front(); nx.pop();
				q.push(a);
				reach[a.x][a.y] = true;
//				printf("%d %d (reach = %d)\n",a.x,a.y,reach[a.x][a.y]);
			}
//			printf("-----------\n");
		}
		++a.lvl;
		q.push(a);
		punct urm = a;
		--urm.x;
		if (valid(urm)) { nx.push(urm); newrch[urm.x][urm.y] = true; add = true; }
		urm.x += 2;
		if (valid(urm)) { nx.push(urm); newrch[urm.x][urm.y] = true; add = true; }
		--urm.x; --urm.y;
		if (valid(urm)) { nx.push(urm); newrch[urm.x][urm.y] = true; add = true; }
		urm.y += 2;
		if (valid(urm)) { nx.push(urm); newrch[urm.x][urm.y] = true; add = true; }
		--urm.y;
	}
}

int main() {
	freopen("castel.in","rt",stdin);
	freopen("castel.out","wt",stdout);

	scanf("%d %d %d",&n,&m,&st);
	--st;
	for (int i = 0; i<n; ++i) {
		for (int j = 0; j<m; ++j) {
			scanf("%d",&rq[i][j]);
			--rq[i][j];
		}
	}

	bf();

	int r = 0;
	for (int i = 0; i<n; ++i) {
		for(int j = 0; j<m; ++j) {
			r += (reach[i][j] || newrch[i][j]);
		}
	}

	printf("%d\n",r);
	return 0;
}