Cod sursa(job #504775)

Utilizator cioboata.iCioboata Ioan Liviu cioboata.i Data 28 noiembrie 2010 17:27:29
Problema Barbar Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include<stdio.h>
const int N=1<<10;
const int M=1<<11;

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

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

struct punct
{
	int lin,col;
};

punct q[N*N];

int xstart,ystart,xfin,yfin,xn,yn;

bool leed(int damage)
{
	int p,u,c;
	bool marcat[N][N]={false};
	p=u=1;
	q[p].lin=xstart;
	q[p].col=ystart;
	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]>=damage && marcat[xn][yn]==false)
			{
				marcat[xn][yn]=true;
				q[++u].lin=xn;
				q[u].col=yn;
				if((q[u].lin==xfin) && (q[u].col==yfin))
					return true;
			}
		}
		p++;
	}
	return false;
}

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

int main()
{
	freopen("barbar.in","r",stdin);
	freopen("barbar.out","w",stdout);
	int m,n,i,j,u,p,c,rez;
	scanf("%d%d\n",&n,&m);
	for(i=1;i<=n;i++)
	{
		a[i][0]=-2;
		a[i][n+1]=-2;
	}
	for(i=1;i<=m;i++)
	{
		a[0][i]=-2;
		a[n+1][i]=-2;
	}
	for(i=1;i<=n;i++)
		gets(&b[i][1]);
	u=0;
	p=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(b[i][j]=='I') { xstart=i; ystart=i; a[i][j]=-1; }
			else if (b[i][j]=='O') { xfin=i; yfin=i; a[i][j]=-1; }
			else if (b[i][j]=='D') { q[++u].lin=i; q[u].col=j; a[i][j]=0; }
			else if (b[i][j]=='*') a[i][j]=-2;
			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]==-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");
	}*/
	rez=cautbin();
	if(rez==0)
	{
		printf("-1");
		return 0;
	}
	printf("%d",rez);
	return 0;
}