Pagini recente » Cod sursa (job #1404093) | Cod sursa (job #2849560) | Cod sursa (job #490747) | Cod sursa (job #1072103) | Cod sursa (job #609629)
Cod sursa(job #609629)
#include<fstream>
#include<vector>
#include<stack>
#include<iostream>
using namespace std;
int n,m,K,xp,yp;
struct Room{short x,y;};
Room a[155][155];
bool key[155][155],vizitat[155][155],acces[155][155];
int sol;
vector <Room> need[155][155];
short dx[]={0,1,0,-1};
short dy[]={1,0,-1,0};
void Citire()
{
int i,j,lim,x,pas;
Room aux,aux2;
ifstream fin("castel.in");
fin>>n>>m>>K;
xp=K/m+1;
yp=K%m;
if(yp==0)
{
xp--;
yp=m;
}
key[xp][yp]=true;
lim=n*m;
i=j=1;
for(pas=1;pas<=lim;pas++)
{
fin>>x;
aux.x=x/m+1;
aux.y=x%m;
if(aux.y==0)
{
aux.x--;
aux.y=m;
}
a[i][j]=aux;
aux2.x=i;
aux2.y=j;
need[aux.x][aux.y].push_back(aux2);
j++;
if(j>m)
{
i++;
j=1;
}
}
fin.close();
}
void DFS()
{
int k;
Room aux,aux2,cheie;
stack <Room> S;
vector <Room>::iterator it;
aux.x=xp;
aux.y=yp;
S.push(aux);
vizitat[xp][yp]=true;
acces[xp][yp]=true;
while(!S.empty())
{
aux=S.top();
S.pop();
key[aux.x][aux.y]=true;
sol++;
for(it=need[aux.x][aux.y].begin();it!=need[aux.x][aux.y].end();it++)
{
aux2=*it;
if(!vizitat[aux2.x][aux2.y] && acces[aux2.x][aux2.y])
{
S.push(aux2);
vizitat[aux2.x][aux2.y]=true;
}
}
for(k=0;k<4;k++)
{
aux2.x=aux.x+dx[k];
aux2.y=aux.y+dy[k];
if(0<aux2.x && aux2.x<=n && 0<aux2.y && aux2.y<=m) //exista camera
{
acces[aux2.x][aux2.y]=true;
cheie=a[aux2.x][aux2.y];
if(!vizitat[aux2.x][aux2.y] && key[cheie.x][cheie.y]) //nu a mai fost vizitata si am cheia
{
S.push(aux2);
vizitat[aux2.x][aux2.y]=true;
}
}
}
}
}
void Afisare()
{
ofstream fout("castel.out");
fout<<sol<<"\n";
fout.close();
}
int main()
{
Citire();
DFS();
Afisare();
return 0;
}