Pagini recente » 11dlabparcurgeri | Cod sursa (job #2108772) | Cod sursa (job #3227766) | Cod sursa (job #1801935) | Cod sursa (job #1164883)
#include <cstdio>
#include <queue>
#include <bitset>
using namespace std;
int n,m,i,j,solution;
struct matrice
{
int val;
bitset<1> vizited;
};
matrice a[155][155];
int v[155][25505];
int curent_keys[25505];
struct coord
{
int x,y,needed_key;
};
coord initial_pozition;
queue<coord> q;
void read()
{
scanf("%d%d%d", &n, &m, &initial_pozition.needed_key);
if(initial_pozition.needed_key%m==0)
{
initial_pozition.x=initial_pozition.needed_key/m;
initial_pozition.y=m;
}
else
{
initial_pozition.x=initial_pozition.needed_key/m+1;
initial_pozition.y=initial_pozition.needed_key-(initial_pozition.x-1)*m;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&a[i][j].val);
v[a[i][j].val][++v[a[i][j].val][0]]=(i-1)*m+j;
}
}
int di[]={0,1,0,-1,0};
int dj[]={0,0,1,0,-1};
bool neighbours(int val)
{
int coord_x,coord_y;
coord_x=val/m+1;
coord_y=val-(coord_x-1)*m;
if(val%m==0)
{
coord_x--;
coord_y=m;
}
if(coord_x<=0||coord_y<=0)
return false;
if(coord_x>n||coord_y>m)
return false;
if(a[coord_x][coord_y].vizited[0]==1)
return false;
int directions;
for(directions=1;directions<=4;directions++)
{
if(a[coord_x+di[directions]][coord_y+dj[directions]].vizited[0]==1)
{
a[coord_x][coord_y].vizited.set();
solution++;
return true;
}
}
return false;
}
bool no_options()
{
int i,j;
bool da=true;
for(i=1;i<=curent_keys[0];i++)
{
for(j=1;j<=v[curent_keys[i]][0];j++)
{
if(neighbours(v[curent_keys[i]][j])==true)
{
curent_keys[++curent_keys[0]]=v[curent_keys[i]][j];
if(curent_keys[0]>n*m)
{
printf("aCEST test imi da programul peste cap\n");
return true;
}
da=false;
}
}
}
return da;
}
int main()
{
freopen("castel.in","r",stdin);
freopen("castel.out","w",stdout);
read();
a[initial_pozition.x][initial_pozition.y].vizited.set();
solution++;
curent_keys[++curent_keys[0]]=initial_pozition.needed_key;
while(!no_options())
{
}
printf("%d",solution);
return 0;
}