Cod sursa(job #418286)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 15 martie 2010 18:48:03
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
//***Infoarena, Castel***//
#include<stdio.h>
#include<vector.h>
using namespace std;
FILE *f=fopen("castel.in","r");
FILE *g=fopen("castel.out","w");
int m,n,k,i,j,p,u,x,y,nr,t,q,w;
vector <int> pos[22502]; // pos[i] -> lista camerelor ce se pot deschide dupa ce avem cheia i
int c[22502];//coada
char viz[22502]; // viz[i]=1 -> camera i a fost vizitata
int a[152][152];
int key[22502]; //key[i]=1 -> am luat cheia i 
int dx[4]={0,1,0,-1}; 
int dy[4]={1,0,-1,0};
int main(){
fscanf(f,"%d%d%d",&n,&m,&k);
for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		fscanf(f,"%d",&a[i][j]);
key[k]=1; //ia cheia din camera initiala
c[1]=k;nr=1;
p=1;u=1; viz[k]=1;
while(p<=u) //cat timp coada s-a terminat
{    //procesam pentru camera c[p]
	if(c[p]%m==0)
		 {x=c[p]/m;
		  y=m;
		 }
	else { x=c[p]/m+1;
		   y=c[p]%m;
			}
	for(i=0;i<pos[c[p]].size();i++) //parcurgem camerele ce se deschid cu cheia a[x][y]
		if(viz[pos[c[p]][i]]==0) //daca nu am verificat-o deja
		{ viz[pos[c[p]][i]]=1;
	        u++;
			nr++;
			key[pos[c[p]][i]]=1;
			c[u]=pos[c[p]][i];
		 }
		t=c[p];
    for(k=0;k<=3;k++) //parcurgem vecinii
	{  if(viz[t+dx[k]*m+dy[k]]==0) //daca este nevizitata
			{  if(key[a[x+dx[k]][y+dy[k]]] && t+dx[k]*m+dy[k]>0 && t+dx[k]*m+dy[k]<=n*m && x+dx[k]>0 && x+dx[k]<=n && y+dy[k]>0 && y+dy[k]<=m) //daca avem cheia si camera este valida
				{ viz[t+dx[k]*m+dy[k]]=1; //marcam ca vizitat
					  u++;
					  c[u]=t+dx[k]*m+dy[k]; //adaugam in coada
					  nr++; //crestem nr de camera in care putem ajunge
					 key[c[u]]=1; //marcam ca fiind luata cheia din camera in care am ajunge
				
				}		
			  else //daca nu avem cheia
				  if(x+dx[k]>0 && x+dx[k]<=n && y+dy[k]>0 && y+dy[k]<=m && t+dx[k]*m+dy[k]<=n*m)
			 pos[a[x+dx[k]][y+dy[k]]].push_back(t+dx[k]*m+dy[k]); //adugam camera ca putand fii deschisa dupa ce avem cheia a[x+dx[k][y+dy[k]]
		} 
	 }
p++;
}
fprintf(g,"%d",nr); //afisam nr de camere	
return 0;
}