Cod sursa(job #582125)

Utilizator crazzytudTudor Popa crazzytud Data 14 aprilie 2011 21:43:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
int a[101][101],b[101][101];
int n,m,min=10001,maxi,maxj;

struct punct{int lin,col;};

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


void bfs1(punct x0)
{
	punct q[100001],x,y;
	int p=1,u=0;
	q[++u]=x0;
	a[x0.lin][x0.col]=1;
	while(p<=u)
	{
		x=q[p++];
		for(int i=0;i<8;i++)
		{
			y.lin=x.lin+dlin[i];
			y.col=x.col+dcol[i];
			if(a[y.lin][y.col]==0)
			{
				a[y.lin][y.col]=a[x.lin][x.col]+1;
				q[++u]=y;
			}
		}
	}
}

void bfs2(punct x0)
{
	punct q[100001],x,y;
	int p=1,u=0;
	q[++u]=x0;
	b[x0.lin][x0.col]=1;
	while(p<=u)
	{
		x=q[p++];
		for(int i=0;i<8;i++)
		{
			y.lin=x.lin+dlin[i];
			y.col=x.col+dcol[i];
			if(b[y.lin][y.col]==0)
			{
				b[y.lin][y.col]=b[x.lin][x.col]+1;
				q[++u]=y;
			}
		}
	}
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	
	int i,j;
	punct x1,x2;
	char c;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%c",&a[i][j]);
			if(a[i][j]==' ')
				a[i][j]=0;
			if(a[i][j]=='X')
				a[i][j]=-1;
			if(a[i][j]=='R')
			{
				x1.lin=i;x1.col=j;
				a[i][j]=-1;
			}
			if(a[i][j]=='J')
			{
				x2.lin=i;x2.col=j;
				a[i][j]=-1;
			}
		}
		scanf("%c",&c);
	}
	
	for(i=0;i<=n+1;i++)
		a[i][0]=a[i][m+1]=-1;
	for(i=0;i<=m+1;i++)
		a[0][i]=a[n+1][i]=-1;
	for(i=0;i<=n+1;i++)
		for(j=0;j<=m+1;j++)
			b[i][j]=a[i][j];
		
	bfs1(x1);
	bfs2(x2);
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			//printf("%d ",a[i][j]);
			if(b[i][j]==a[i][j]&&a[i][j]!=-1&&a[i][j]!=0&&a[i][j]<min)
			{
				min=a[i][j];
				maxi=i;
				maxj=j;
			}			
		}
		//printf("\n");
	}
	
	/*printf("\n\n\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			printf("%d ",b[i][j]);
		}
		printf("\n");
	}
	*/
	printf("%d %d %d",min,maxi,maxj);
	return 0;
}