Pagini recente » Cod sursa (job #1543965) | Cod sursa (job #2548704) | Cod sursa (job #843227) | Cod sursa (job #2301489) | Cod sursa (job #1641586)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
int di[4]={-1,0,1,0};
int dj[4]={0,1,0,-1};
queue < pair < int, int > > coada;
int castel[150][150];
int camDeschise[150][150];
int n,m,k,istart,jstart,nrchei,directie,r, chei[200];
void CoordCamera(int k){
int i,j,rest;
rest=k%m;
if (rest==0){
i=k/m;
j=m;
}
if (rest>0){
i=k/m+1;
j=rest;
}
istart=i;
jstart=j;
}
int Verificare(int i, int j){ // modul de generare a unei chei pentru celula i-j
return (i-1)*n+j;
}
bool OK(int i, int j, int q){ // verifica daca celula i-j indeplineste conditiile de continuare
if (i<1 || j<1 || i>m || j>n)
return 0;
for (r=1;r<=q;r++)
if (chei[r]==castel[i][j])
{
return 1;
}
return 0;
}
bool continua(int i, int j, int q){ // se verifica daca celula i-j ce genereaza o cheie se regaseste deja in vecorul cheii
for (r=1;r<=q;r++)
if (chei[r]==Verificare(i,j))
{
return 0;
}
return 1;
}
void cit(){
fin>>m>>n>>k;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
fin>>castel[i][j];
}
void lee(){
int i,j,iu,ju;
camDeschise[istart][jstart]=1;
nrchei=1; // nr de chei de acces
chei[nrchei]=k; // vectorul in care se retin cheile de acces
coada.push(make_pair(istart,jstart));
while (!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for (directie=0;directie<4;directie++)
{
iu=i+di[directie];
ju=j+dj[directie];
if (OK(iu,ju,nrchei))
{
if (continua(iu,ju,nrchei) && camDeschise[iu][ju]<1) // pentru prima parcurgere unde se genereaza o noua cheie
{
camDeschise[iu][ju]=camDeschise[i][j]+1;
nrchei++;
chei[nrchei]=Verificare(iu,ju);
coada.push(make_pair(iu,ju));
}
else
// <=4 deoarece se poate patrunde intr-o celula din maxim 4 directii.
if (camDeschise[iu][ju]<=4) // numai pentru celulele prin care s-a mai trecut cel putin o data si deja s-a generat o cheie
{
camDeschise[iu][ju]=camDeschise[i][j]+1;
coada.push(make_pair(iu,ju));
}
}
}
}
}
int main()
{
cit();
CoordCamera(k);
lee();
fout<<nrchei;
}