Pagini recente » Cod sursa (job #2346341) | Cod sursa (job #1068877) | Cod sursa (job #2314885) | Cod sursa (job #1698361) | Cod sursa (job #418286)
Cod sursa(job #418286)
//***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;
}