Cod sursa(job #244867)

Utilizator zlatebogdanZlate Bogdan zlatebogdan Data 16 ianuarie 2009 10:39:37
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<string.h>
#define N 105
int n,m,xr,xj,yr,yj,b[N][N],c[N][N],min,xx,yy;
char a[N][N];
const int dlin[]={-1,0,1,0,-1,1,1,1};
const int dcol[]={0,1,0,-1,-1,-1,1,-1};
void init(int z[N][N])
{
	int i,j;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (a[i][j]==' ')
				z[i][j]=1;
}
void citire()
{
	int i,j;
	scanf("%d %d\n",&n,&m);
	for (i=1;i<=n;++i)
		gets(a[i]+1);
	for(i=0;i<=n+1;++i)
		a[i][0]=a[i][m+1]='X';
	for(j=0;j<=m+1;++j)
		a[0][j]=a[n+1][j]='X';	
}
void caut()
{
	int i,j;
	for (i=1;i<=n;++i)
	{
		for (j=1;j<=m;++j)
		{
			if (a[i][j]=='R')
			{
				xr=i;
				yr=j;
			}
			if (a[i][j]=='J')
			{
				xj=i;
				yj=j;
			}
		}
			
	}
}
void bfs(int x,int y, int o[N][N])
{
	int i,p,u,coada[N][2],z[2],t[2];
	p=u=0;
	coada[u][0]=x;
	coada[u++][1]=y;
	o[x][y]=1;
	while (p!=u)
	{
		z[0]=coada[p][0];
		z[1]=coada[p++][1];
		for (i=0;i<8;++i)
		{
			t[0]=z[0]+dlin[i];
			t[1]=z[1]+dcol[i];
			if (o[t[0]][t[1]]==0 && a[t[0]][t[1]]!='X')
			{
				coada[u][0]=t[0];
				coada[u++][1]=t[1];
				o[t[0]][t[1]]=1+o[z[0]][z[1]];
			}
		}
	}
}
void afis(int z[N][N])
{
	int i,j;
	for (i=1;i<=n;++i)
	{
		for(j=1;j<=m;++j)
			printf("%3d",z[i][j]);
		printf("\n");
	}
	printf("\n");
}
void cautare()
{
	int i,j;
	min=1000000;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (c[i][j] && c[i][j]==b[i][j]&&c[i][j]<min)
			{
				min=c[i][j];
				xx=i;
				yy=j;
			}
	printf("%d %d %d\n",min,xx,yy);
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	citire();
	caut();
	bfs(xr,yr,b);
	bfs(xj,yj,c);
	afis(b);
	afis(c);
	cautare();
	return 0;
}