Pagini recente » Cod sursa (job #1538445) | Cod sursa (job #1703879) | Cod sursa (job #222836) | Cod sursa (job #2593931) | Cod sursa (job #609620)
Cod sursa(job #609620)
#include<fstream>
#include<iostream>
#include<queue>
using namespace std;
int n,m,K,xp,yp;
struct Room{short x,y;};
Room a[155][155];
bool key[155][155];
int vizitat[155][155];
int nrsol[1000000];
int sol;
short dx[]={0,1,0,-1};
short dy[]={1,0,-1,0};
void Citire()
{
int i,j,lim,x,pas;
Room aux;
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;
j++;
if(j>m)
{
i++;
j=1;
}
}
fin.close();
}
void BFS()
{
int k,pas;
Room aux,aux2,cheie;
queue <Room> Q;
aux.x=xp;
aux.y=yp;
Q.push(aux);
vizitat[xp][yp]=true;
sol=1;
nrsol[1]=sol;
pas=2;
while(!Q.empty())
{
aux=Q.front();
Q.pop();
key[aux.x][aux.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
{
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
{
sol++;
Q.push(aux2);
vizitat[aux2.x][aux2.y]=pas;
nrsol[pas]=sol;
pas++;
}
else
if(vizitat[aux2.x][aux2.y] && sol!=nrsol[vizitat[aux2.x][aux2.y]])
{
Q.push(aux2);
vizitat[aux2.x][aux2.y]=pas;
nrsol[pas]=sol;
pas++;
}
}
}
}
}
void Afisare()
{
ofstream fout("castel.out");
fout<<sol<<"\n";
fout.close();
}
int main()
{
Citire();
BFS();
Afisare();
return 0;
}