Cod sursa(job #727610)

Utilizator swim406Teudan Adina swim406 Data 28 martie 2012 09:42:58
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>
using namespace std;
struct matrice {
	int nr, key;
};
int check[155][155],keys[22510],end=0,m,n,ok[155][155];
matrice M[1515][155];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void drum(int a, int b) {
	int i,x,y;
	for(i=0;i<4;i++) 
		if(M[a+dx[i]][b+dy[i]].nr!=-1) {
			x=a+dx[i];
			y=b+dy[i];
			if(check[x][y]==0)
				if(keys[M[x][y].key]) {
					keys[M[x][y].nr]=1;
					if(!ok[x][y]) {
						end=0;
						ok[x][y]=1;
					}
					if(check[x][y]!=1)
						check[x][y]=1;
					drum(x,y);
				}
		}
}
int main() {
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	int k,x,y,p,count=0,i,j;
	scanf("%d %d %d",&m,&n,&k);
	for(i=1;i<=m;i++) 
		for(j=1;j<=n;j++) 
			scanf("%d",&M[i][j].key);
	for(i=1;i<=n;i++){
		M[1][i].nr=i;
		if(i==k) {
			x=1;
			y=i;
		}
	}
	p=i;
	for(i=0;i<=m+1;i++) {
		M[i][0].nr=-1;
		M[i][n+1].nr=-1;
	}
	for(i=0;i<=n+1;i++) {
		M[0][i].nr=-1;
		M[m+1][i].nr=-1;
	}
	for(i=2;i<=m;i++) 
		for(j=1;j<=n;j++) {
			M[i][j].nr=p;
			if(p==k) {
				x=i;
				y=j;
			}
			p++;
		}
	ok[x][y]=1;
	keys[M[x][y].nr]=1;
	while(!end) {
		end=1;
		for(i=0;i<=m+1;i++)
			for(j=0;j<=n+1;j++)
				check[i][j]=0;
		check[x][y]=1;
		drum(x,y);
	}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(ok[i][j]==1) 
				count++;
	printf("%d\n",count);
		/*	for(i=0;i<=m+1;i++) {
				for(j=0;j<=n+1;j++)
					printf("%d ",M[i][j].key);
				printf("\n");
			}
	for(i=1;i<=p-1;i++) printf("%d ",keys[i]);*/
	return 0;
}