Pagini recente » Cod sursa (job #2360773) | Cod sursa (job #3266195) | Cod sursa (job #2500873) | Cod sursa (job #223197) | Cod sursa (job #598305)
Cod sursa(job #598305)
// VA ROG IGNORATI SURSA. TESTEZ TIMPU DE EXECUTIE
#include<stdio.h>
#define LMAX 1569
#define maxim(a,b) ((a) > (b) ? (a) : (b))
#include<queue>
short int n,m,x[LMAX][LMAX],f1[LMAX][LMAX],f2[LMAX][LMAX];
bool used[LMAX][LMAX];
struct pozdy
{
int x,y;
};
int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
using namespace std;
queue<pozdy> Q;
inline pozdy make_pozdy(int x0,int y0)
{
pozdy aux;
aux.x=x0;
aux.y=y0;
return aux;
}
void solve(pozdy aux,short int f[LMAX][LMAX])
{
int i,cst;
while(!Q.empty())
Q.pop();
Q.push(aux);
while(!Q.empty())
{
aux=Q.front();
for(i=aux.x;i>=1;i--)
{
cst=maxim(f[aux.x][aux.y]+1,x[i][aux.y]);
if(f[i][aux.y]==0 || cst<f[i][aux.y])
{
Q.push(make_pozdy(i,aux.y));
f[i][aux.y]=cst;
}
}
for(i=aux.x;i<=n;i++)
{
cst=maxim(f[aux.x][aux.y]+1,x[i][aux.y]);
if(f[i][aux.y]==0 || cst<f[i][aux.y])
{
Q.push(make_pozdy(i,aux.y));
f[i][aux.y]=cst;
}
}
for(i=aux.y;i>=1;i--)
{
cst=maxim(f[aux.x][aux.y]+1,x[aux.x][i]);
if(f[i][aux.y]==0 || cst<f[i][aux.y])
{
Q.push(make_pozdy(aux.x,i));
f[aux.x][i]=cst;
}
}
for(i=aux.y;i<=m;i++)
{
cst=maxim(f[aux.x][aux.y]+1,x[aux.x][i]);
if(f[i][aux.y]==0 || cst<f[i][aux.y])
{
Q.push(make_pozdy(aux.x,i));
f[aux.x][i]=cst;
}
}
Q.pop();
}
}
void BF()
{
int i,j;
pozdy aux,now;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(x[i][j]==0)
Q.push(make_pozdy(i,j));
while(!Q.empty())
{
aux=Q.front();
for(i=0;i<4;i++)
{
now.x=aux.x+dx[i];
now.y=aux.y+dy[i];
if(x[now.x][now.y]==-2)
{
x[now.x][now.y]=x[aux.x][aux.y]+1;
Q.push(now);
}
}
Q.pop();
}
}
int main()
{
int i,j;
char ch;
pozdy p1,p2;
p1.x=p1.y=0;
freopen("lbd.in","r",stdin);
freopen("lbd.out","w",stdout);
/*scanf("%d%d\n",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%c",&ch);
if(ch=='.')
x[i][j]=0;
if(ch=='X')
x[i][j]=-2;
if(ch=='L')
{
if(!p1.x && !p1.y)
p1.x=i, p1.y=j;
else
p2.x=i, p2.y=j;
}
}
scanf("\n");
} */
//BAG TESTELE DE MANA
n=69; m=69;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(i!=1 && j!=1 && i!=n && j!=m)
x[i][j]=-2;
else
x[i][j]=0;
BF();
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
printf("%d ",x[i][j]);
printf("\n");
}
/*solve(p1,f1);
solve(p2,f2);
int min=1<<30,ma;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
ma=max(f1[i][j],f2[i][j]);
if(ma<min)
min=ma;
}
printf("%d",min); */
return 0;
}