Cod sursa(job #504353)

Utilizator cioboata.iCioboata Ioan Liviu cioboata.i Data 27 noiembrie 2010 15:32:59
Problema Barbar Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include<cstdio>
const int N=1<<8;
const int M=1<<12;

int a[N][N];
char b[N][N];

int xbun,ybun,xstart,ystart,n,m;

int dlin[]={0,1,0,-1};
int dcol[]={-1,0,1,0};

struct punct
{
	int lin,col;
};

punct q[N*N];

bool gigi(int damage)
{
	int c,u,p,xn,yn;
	bool marcat[N][N] = {false};
	p = u = 1;
	q[1].lin = xstart;
	q[1].col= ystart;
	marcat[xstart][ystart] = true;
	while( p<=u)
	{
		for(c=0;c<=3;c++)
		{
			xn=q[p].lin+dlin[c];
			yn=q[p].col+dcol[c];
			//if( a[xn][yn]!=-2 &&  a[xn][yn]!=0 && ( a[xn][yn]==-1 || a[q[p].lin][q[p].col]+1 < a[xn][yn]) )
			if(a[xn][yn]>=damage && !marcat[xn][yn])
			{	
				//a[xn][yn]=a[q[p].lin][q[p].col]+1;
				marcat[xn][yn] = true;
			    q[++u].lin=xn;
				q[u].col=yn;
				if(xn == xbun && yn == ybun)
					return true;
			}
		}
		p++;
	}
	/*
	for(int i=1 ; i<=n ; ++i)
	{
		for(int j=1 ; j<=m ; ++j)
			printf("%3d",marcat[i][j]);
		printf("\n");
	}
	printf("\n");
	*/
	return false;
}

int cautbin ( )
{
	int pas=M,i;
	for(i=0 ; pas!=0 ; pas>>=1)
		if(gigi(i+pas))
			i += pas;
	return i;
}

int main()
{
	freopen("barbar.in","r",stdin);
	freopen("barbar.out","w",stdout);
	int i,j,u,p,c,xn,yn;
	scanf("%d %d\n",&n,&m);
	for(i=0;i<=n+1;i++)
	{
		b[0][i]=-1;
		b[n+1][i]=-1;
		b[i][0]=-1;
		b[i][n+1]=-1;
	}
	u=0;
	p=1;
	for(i=1;i<=n;i++)
		gets(&b[i][1]);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(b[i][j]=='D') 
			{
				a[i][j]=0;
				q[++u].lin=i;
				q[u].col=j;
			}
			else if (b[i][j]=='*') a[i][j]=-2;
			else if(b[i][j]=='O') { xbun=i; ybun=j; a[i][j]=-1;}
			else if(b[i][j]=='I') { xstart=i; ystart=j; a[i][j]=-1;}
			else a[i][j]=-1;
		}
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			printf("%3d",a[i][j]);
		printf("\n");
	}
	printf("\n");*/
	while( p<=u)
	{
		for(c=0;c<=3;c++)
		{
			xn=q[p].lin+dlin[c];
			yn=q[p].col+dcol[c];
			//if( a[xn][yn]!=-2 &&  a[xn][yn]!=0 && ( a[xn][yn]==-1 || a[q[p].lin][q[p].col]+1 < a[xn][yn]) )
			if(a[xn][yn]==-1)
			{	
				a[xn][yn]=a[q[p].lin][q[p].col]+1;
			    q[++u].lin=xn;
				q[u].col=yn;
			}
		}
		p++;
	}
	
	
	
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			printf("%3d",a[i][j]);
		printf("\n");
	}*/

	printf ("%d",cautbin());
	return 0;
}