Cod sursa(job #203485)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 16 august 2008 22:19:43
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
#define N 151
int m,n,k,xs,ys;
int a[N][N],*c[N*N],viz[N][N],sol=1;
const int lin[]={0,0,1,-1};
const int col[]={1,-1,0,0};
//c[i]=camerele in care pot patrunde la pasul curent daca as avea cheia i
//c[i][0]=cate camere sunt
//c[i][1]=am patruns in primele c[i][1] camere
void adauga(int x,int y,int p){
	c[p][0]++;
	c[p]=(int*)realloc(c[p],(c[p][0]+1)*4);
	c[p][c[p][0]]=(x-1)*n+y;
}
void solve(int x,int y){
	viz[x][y]=1;int xx,yy;
	for(int t=0;t<4;t++)
		if(!viz[x+lin[t]][y+col[t]]){
			if(a[x+lin[t]][y+col[t]]%n==0) xx=a[x+lin[t]][y+col[t]]%n,yy=n;
			else xx=a[x+lin[t]][y+col[t]]/n+1,yy=a[x+lin[t]][y+col[t]]%n;
			if(viz[xx][yy]){ //daca am cheia pt camera cu coord x+lin[t],y+col[t]
				sol++;
				viz[x+lin[t]][y+col[t]]=1;
				solve(x+lin[t],y+col[t]);
			}
			else adauga(x+lin[t],y+col[t],a[x+lin[t]][y+col[t]]);
		}
	int xy=(x-1)*n+y;
	for(int i=c[xy][1]+1;i<=c[xy][0];i++){
		if(c[xy][i]%n==0) x=c[xy][i]/n,y=n;
		else x=c[xy][i]/n+1,y=c[xy][i]%n;
		if(!viz[x][y]){
			viz[x][y]=1;
			sol++;
			solve(x,y);
		}
	}
}
	
int main(){
	int x,i,j,y;
	freopen("castel.in","r",stdin);
	freopen("castel.out","w",stdout);
	scanf("%d%d%d",&m,&n,&k);
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++){
			scanf("%d",&x);
			a[i][j]=x;
		}
	for(i=1;i<=m*n;i++) 
		c[i]=(int*)malloc(8),c[i][0]=c[i][1]=1;
	for(i=1;i<=m;i++) viz[i][n+1]=viz[i][0]=1;
	for(i=1;i<=n;i++) viz[0][i]=viz[m+1][i]=1;
	if(k%n==0) 
		x=k/n,y=n;
	else x=k/n+1,y=k%n;
	viz[x][y]=1;
	solve(x,y);
	printf("%d\n",sol);
	return 0;
}