Pagini recente » Cod sursa (job #253054) | Cod sursa (job #1210874) | Cod sursa (job #2972685) | Cod sursa (job #2904099) | Cod sursa (job #717512)
Cod sursa(job #717512)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
struct pozitie
{
int x;
int y;
};
int n, m;
bool inside(int i, int j)
{
return i>=1 && j>=1 && i<=n && j<=m;
}
pozitie camera[62502],vecin[62502];
bool vizitat[152][152],vecin_here[152][152];
int nrcam,gata;
vector<int> cheie;
void update_vecin(pozitie v)
{
if(binary_search(cheie.begin(),cheie.end(),(v.x-1)*m+v.y))
{
camera[++nrcam].x=v.x;
camera[nrcam].y=v.y;
}
vecin_here[v.x][v.y]=false;
gata=0;
}
int main()
{
int x,i,j,a[151][151],in,k,nrvecin=0,inou,jnou,t;
fin>>n>>m>>x;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fin>>a[i][j];
cheie.push_back(x);
i=x/m+1;
j=x%m;
vizitat[i][j]=true;
camera[1].x=i;
camera[1].y=j;
nrcam=1;
t=1;
while(!gata)
{
gata=2;
for( ;t<=nrcam;t++)
{
for(k=0;k<4;k++)
{
inou=camera[t].x+di[k];
jnou=camera[t].y+dj[k];
if(inside(inou,jnou) && !vizitat[inou][jnou])
{
if(binary_search(cheie.begin(),cheie.end(),a[inou][jnou]))
{
camera[++nrcam].x=inou;
camera[nrcam].y=jnou;
vizitat[inou][jnou]=true;
cheie.push_back((inou-1)*m+jnou);
sort(cheie.begin(),cheie.end());
gata=0;
}
else
{
vecin[++nrvecin].x=inou;
vecin[nrvecin].y=jnou;
vecin_here[inou][jnou]=true;
}
}
}
}
for(in=1;in<=nrvecin;in++)
{
inou=vecin[in].x;
jnou=vecin[in].y;
if(vecin_here[inou][jnou])
update_vecin(vecin[in]);
}
}
fout<<nrcam;
fin.close();
fout.close();
return 0;
}
/*
gata=1;
for(in=1;in<=nrvecin;in++)
{
i=vecin[in].x;
j=vecin[in].y;
for(k=0;k<4;k++)
if(inside(i+di[k],j+dj[k])
&& !vizitat[i+di[k]][j+dj[k]])
if(binary_search(cheie.begin(),cheie.end(),a[i+di[k]][j+dj[k]]))
{
camera[++nrcam].x=i+di[k];
camera[nrcam].y=j+dj[k];
vizitat[i+di[k]][j+dj[k]]=true;
cheie.push_back((i+di[k]-1)*m+j+dj[k]);
sort(cheie.begin(),cheie.end());
gata=0;
}
else
{
vecin[++nrvecin].x=i+di[k];
vecin[++nrvecin].y=j+dj[k];
}
}
*/